算法面試真題詳解：合并k個排序數組

将 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