Given multiple sorted arrays, what's the most efficient way to collect the K largest values from all of them?
For example:
Input:
K = 5
array1: [100, 50, 30, 20, 10]
array2: [400, 50, 20, 0]
array3: [0, 0, 0, 0]
Output:
[400, 100, 50, 50, 30]
Thanks.
CodePudding user response：
Put all arrays in a priority queue (so in the example, the priority queue would have three values), keyed by the first value in those arrays. Use an efficient implementation for the priority queue, like a binary heap.
As you pop an item from the queue, extract the first value from the corresponding array*, and if the array is not empty yet, insert it again into the priority queue, now keyed by its current first element.
Do this K times to get the first K values.
*To avoid a non-constant time complexity, instead of really pulling out that value from the array, you can maintain an iterator over the array (like an index that increments...).
CodePudding user response：
Here's an O((N K) * log N) solution, where N is the number of arrays.
First, create a max heap by taking the highest element of each of the N arrays, which can be done in O(N * log N) time.
Then, for K iterations:
Pop off the top of the heap in O(log N) and insert the element of the corresponding array that follows the one that was just popped off in O(log N).
The loop does O(log N) work hence the complexity is O((N K) * log N)