Merge K sorted array into one big sorted array in ascending order.
Assumptions
- The input arrayOfArrays is not null, none of the arrays is null either.
注意matrix每一行length可能不等,可能不为0
public int[] merge(int[][] arrayOfArrays) {
//注意不能包括第二个条件,因为有可能只是第一行为空
if (arrayOfArrays.length == 0 /*|| arrayOfArrays[0].length == 0 */) {
return new int[0];
}
int size = 0;
for (int i = 0; i < arrayOfArrays.length; i++) {
size += arrayOfArrays[i].length;
}
int[] ans = new int[size];
PriorityQueue<Pair> pq = new PriorityQueue<>(1, new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
return a.val - b.val;
}
});
for (int i = 0; i < arrayOfArrays.length; i++) {
if (arrayOfArrays[i].length > 0) {
pq.offer(new Pair(arrayOfArrays[i][0], i, 0));
}
}
int index = 0;
while (!pq.isEmpty()) {
Pair cur = pq.poll();
ans[index++] = cur.val;
if (cur.y + 1 < arrayOfArrays[cur.x].length) {
pq.offer(new Pair(arrayOfArrays[cur.x][cur.y + 1], cur.x, cur.y + 1));
}
}
return ans;
}
class Pair {
int val, x, y;
public Pair(int val, int x, int y) {
this.val = val;
this.x = x;
this.y = y;
}
}