k sorted array can be merged in linear time I believe. If we have K arrays FIRST, SECOND, ....., Up to K and we keep k counters (i, j, ...., up to k), one for each list
Simply check if FIRST[i] < SECOND[j], ....., Up to K Put the smallest in the merged list and increment the counter of the list it came from, keep doing this until you've read each array once and you will have a sorted list On 25 March 2011 08:06, bittu <[email protected]> wrote: > Given k sorted arrays each of length n, construct a single merged and > sorted array.focus on running time and space complexity > > my soln. 1st basic soln..simple merge sort all whet we does in merging > 2 sorted array it too complex for big K > 2nd i have approach using min-heap as well but not able to figure the > working code ..dono why? > > lets c what others think > > Approach & Exactness of The Solution matters here > > > Thanks > Shashank > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
