将 k 个有序数组合并为一个大的有序数组。
在线评测地址：领扣题库官网
样例 1:
Input:
[
[1, 3, 5, 7],
[2, 4, 6],
[0, 8, 9, 10, 11]
]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]样例 2:
Input:
[
[1,2,3],
[1,2]
]
Output: [1,1,2,2,3]算法一 暴力
题目指出k个数组是有序的，那我们可以借鉴归并排序的思想
每次遍历k个有序数组的数组第一个元素，找出最小的那个，然后压入答案ans数组，记得把最小的那个从它原先的数组给删除
每次找最小的是O(K)的，所以总复杂度是O(NK)的，N是k个数组的所有元素的总数量
算法二 优先队列优化
根据算法一，来进行优化，我们可以通过一些有序集合来找最小值，比如set map 堆 平衡树一类都可以，我们这里用堆来加速求最小值的操作
优先队列
- 先将每个有序数组的第一个元素压入优先队列中
- 不停的从优先队列中取出最小元素（也就是堆顶），再将这个最小元素所在的有序数组的下一个元素压入队列中 eg. 最小元素为x，它是第j个数组的第p个元素，那么我们把第j个数组的第p+1个元素压入队列
复杂度分析
时间复杂度
因为一开始队列里面最多k个元素，我们每次取出一个元素，有可能再压入一个新元素，所以队列元素数量的上限就是K，所以我们每次压入元素和取出元素都是logK的，因为要把k个数组都排序完成，那么所有元素都会入队 再出队一次，所以总共复杂度是$(NlogK) N是K个数组里面所有元素的数量
空间复杂度
开辟的堆的空间是O(K)的，输入的空间是 O(N),总空间复杂度O(N+K)
public class Solution {
/**
* @param arrays: k sorted integer arrays
* @return: a sorted array
*/
static class Node implements Comparator<Node> {
public int value;
public int arrayIdx;
public int idx;
public Node() {
}
//value权值大小，arraysIdx在哪个数组里，idx在该数组的哪个位置> >
public Node(int value, int arrayIdx, int idx) {
this.value = value;
this.arrayIdx = arrayIdx;
this.idx = idx;
}
public int compare(Node n1, Node n2) {
if(n1.value < n2.value) {
return 1;
} else {
return 0;
}
}
}
static Comparator<Node> cNode = new Comparator<Node>() {
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
};
public int[] mergekSortedArrays(int[][] arrays) {
// 初始化 优先队列 ，我们优先队列的一个元素包括三个值 ：数字大小，数字在哪个数组里，数字在数组的哪个位置
PriorityQueue<Node> q = new PriorityQueue<Node>(arrays.length + 5, cNode);
// 初始化 答案
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < arrays.length; i++) {
// 如果这个数组为空 则不用压入
if(arrays[i].length == 0) {
continue;
}
// arrays[i][0] 权值大小 i 在第i个数组 0 在该数组的0位置
q.add(new Node(arrays[i][0], i, 0));
}
while(!q.isEmpty()) {
// 取出队列中最小值
Node point = q.poll();
// 权值 ，所在数组的编号，在该数组的位置编号
int value = point.value;
int arrayIdx = point.arrayIdx;
int idx = point.idx;
// 更新答案数组
ans.add(value);
// 它已经是所在数组的最后一个元素了，这个数组的所有元素都已经处理完毕
if(idx == arrays[arrayIdx].length - 1) {
continue;
} else {
// 压入它下一个位置的新元素
Node newPoint = new Node(arrays[arrayIdx][idx + 1], arrayIdx, idx + 1);
q.add(newPoint);
}
}
return ans.stream().mapToInt(Integer::valueOf).toArray();
}
}更多题解参考：九章官网solution
