Problem
Merge A List Of Sorted Arrays
Write a program that takes as input a set of sorted sequences and computes the union of these sequences as a sorted sequence. For example, if the input is [3, 5, 7], [0, 6], and [0, 6, 28], then the output is [0, 0, 3, 5, 6, 6, 7, 28].
Solution
The problem is asking for general solution, though we can start with 3 array cases, but eventually the solution should handle N array.
Brutal force solution is to copy them all into a new array, then run NlongN sort. However, since the arrays are sorted, we only need k pointers to trace which array has the smallest element compare to the rest of the k - 1. We can use a priority queue to keep track of the smallest element. Priority queue use heap sort to support O(1) cost smallest element retrieval, with k sized priority queue, the sink and swim operation cost is klogk. So the total time cost will be Nklogk, the extra space cost is O(k) which is the space occupied by the priority queue.
import java.util.*;
public class MergeSortedArrays {
public static int[] sort(int[][] arrays) {
//[3, 5, 7], [0, 6], and [0, 6, 28]
int k = arrays.length; //3
int N = 0;
for(int[] array : arrays) {
N += array.length;
}
int[] result = new int[N]; //8
int r = 0;
Queue<int[]> pq = new PriorityQueue<>(k, (i, j) -> arrays[i[0]][i[1]]-arrays[j[0]][j[1]]);
for(int i = 0; i < arrays.length; i++) {
pq.offer(new int[]{i, 0}); // 2 1, 0 2
}
while(!pq.isEmpty()) {
int[] t = pq.poll(); //1 1
int arrSeq = t[0];
int curIndex = t[1];
result[r++] = arrays[arrSeq][curIndex]; //[0, 0, 3, 5, 6]
if(curIndex < arrays[arrSeq].length - 1) {
pq.offer(new int[]{arrSeq, ++curIndex});
}
}
return result;
}
public static void main(String...args) {
int[][] arrays = new int[][] {
{3, 5, 7},
{0, 6},
{0, 6, 28}
};
int[] result = sort(arrays);
System.out.println(result.length);
Arrays.stream(result).forEach(i -> System.out.print(i + " "));
}
}
Time cost O(Nklogk), extra space O(k)
