@Dave: Very nice. If you merge pairs of rows and throw out dupicates, I believe that is also O(m*n*log(m)). It takes log(m) times merging all of the rows. The number and length of the rows changes, but the total number of elements will be m*n or less.
Don On Jan 8, 3:16 pm, Dave <[email protected]> wrote: > @Ravi: Construct a min-heap of the elements of the first column, each > appended with its row and column number, i.e., form a heap whose elements > contain (a[i][0], i, 0). > While the heap is not empty: > Output the top element of the heap. > Insert the next element from its row, if any. > If the output array is empty, or if the outputted heap top is different > from the last element in the output array, > then insert the outputted heap top into the output array. > > Complexity is m*n*log(m). > > Dave > > > > > > > > On Tuesday, January 8, 2013 11:59:55 AM UTC-6, Ravi Ranjan wrote: > > You have a two dimensional array of size m*n. The > > elements in the rows are sorted and every row has > > unique elements means( in a row no two elements are same) but > > the elements can repeat across the rows. > > For example: > > you have following 2-D array: > > 2 5 7 9 14 16 > > 3 6 8 10 15 21 > > 4 7 9 15 22 35 > > 7 8 9 22 40 58 > > You are supposed to write an efficient function which > > will take upper 2-D array as input and will return a > > one-dimensional array with following properties: > > a) the 1-D array must contain all the elements of above > > 2-D array. > > b) the 1-D array should not have any repeated elements. > > c) all the elements should be in sorted order. > > For example: > > for the above 2-D array, the output should be: > > A [ ] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35, > > 40, 58 } --
