Menu
Possible Duplicates:
Merging two sorted lists
Algorithm for N-way merge
Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity.
Source : Amazon interview question.
Any thoughts? thanks
331
To use merge sort to remove duplicates, you would ignore elements that are repeated in the merging process. This reply answered the question recusively. take a look at the instructions for Mergesort.
Method 1: By traversing both the arrays to keep track of the current element in each arrays and finding the minimum value among the two and updating the output_array with the least value. Method 2: Concatenate the two arrays into one and then sorting the entire array. Method 3: Another approach is by using min-heaps.
Make a heap from the first element in each array. Pop the head element from the heap, insert it into the result array, and then take the next element from the array the head of the heap came from, and insert that into the heap. Repeat until you consume all of the arrays.
196
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
