将 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();     }  } 

大佬有話說 (0)