@Sharad. Haven't you changed the roles of n and k? The original poster
had n lists with average length k, meaning a total of n*k elements.
You have k lists with a total of n elements, meaning that each list
has an average of n/k elements.
Dave
On Jul 3, 1:02 pm, sharad kumar <sharad20073...@gmail.com> wrote:
> 1. First take two lists at a time and merge them so total elements parsed
> for all lists =O(n)
> This operation results in k/2 lists
> 2. Repeat steps till k/2 == 1.
>
> *Time complexity of above solution = O(n logk)*
> Step1 would loop through *logk *times and each operation would require
> parsing all n elements in all the lists for making k/2 lists
>
> eg:: if i had 8 lists then first pass would make 4 lists by parsing all n
> elements; second pass would make 2 lists by parsing again n elements and
> third pass would give 1 list again by parsing n elements.
>
> *Constraint of the above Solution*
> For merging we would require *O(n) *extra space.
>
> *Solution2: Without Using O(n) extra space; uses O(k) extra space*
> **j = 1;
> 1. (For all lists L[i])
> {
> Take the jth element from each list and create a min heap in O(k) with the
> node data and
> index information. Take the minimum element from the heap in O(1) i.e. root
> node and put
> it in *List1 indexj.*
> **if the element didn't belong to list1[j] then swap it with list1[j] with
> list to which the min
> element belonged.
> Now increment the pointer j for the list l1(or to the list where in the min
> nodes are getting added) and add the new node to min heap}
>
> 2. Keep repeating steps 1 till all n elements are being looked up
>
> *Time Complexity = O(n logk ) SPACE = O(k)*
> At a time we have k elements min heap and for all n elements we have to
> readjust the heap in log(k) time so total time = *O(n logk )* and space used
> = *O(k)*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
