Solution To 1st problem
maintain two single dimension arrays...initially store 1st rows in both arrays from both input arrays
find minimum element in stored array it takes O(n) time
replace that minimum ele with correspondin column next element
[ Example if a[0][0] is minimum replace with a[1][0] ]
like this repeat upto finding n2 elements
algoithm
for i=0 to n {
minarr1[i] = arr1[0][i];
}
for i=0 to n {
minarr2[i] = arr2[0][i];
}
free1 =0, free2 =0;
for i <- 1 to n*n {
if free1 is 0
find minimum ele from arr1 and store min1;
if free2 is 0
find minimum element from arr2 and store min2;
if min1 > min2
free1=1;
free2=0;
store min2 in new array
else
free1=0;
free2=0;
store min1 in new array
}
On 8/4/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]
> wrote:
Consider a Array of N x N
For example take 3 X 3
Since the array is sorted by row and column , sort all the array
elements by reading it in zig-zag order.
for example
5 8 9
6 10 13
11 15 17
can be read as
5 6 8 9 10 11 13 15 17
by chechking whether the row or column entry contains smaller number
when reading in zig zag order.
After the two given N x N array are sorted , merge the two using sorted
outputs
Take the first N of final merged sorted array and arrange it in zig azg
order
It contains the least N^2 elements from the two given array
and the median is the centre element ie.,(N/2,N.2) of the array
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
