1439. 有序矩阵中的第 k 个最小数组和 (opens new window)

1.有序队列(暴力)

将大问题拆分成子问题的问题思考角度。如果当前数组前i行已经得到最小的k个子数组，那么第i+1行的最小k个子数字该如何计算？这里需要将第i行的所有数字依次与当前最小的k个字数组和相加，也就是说会得到k*mat[0].length个结果，然后将结果排序并从中取出k个最小的数组和。

• ⚡⚡⚡求和时第i行的所有数字都需要进行相加，因为可能存在【第i行第一个元素与队列最大的数组和】比【第i行最后一个元素与队列最小的数组和】大的情况。
• list集合保存前i行k个数组和，curr保存当前第i+1行加入后所有可能的数组和结果
• 每次遍历需要从curr的结果中选出最小的k个写入到list中
• 对集合排序可以使用Collections.sort；也可以使用数组的排序Arrays.copyOfRange(nums,from,to)

缺点：没有使用上数组每行都是有序的这个条件。

class Solution {
    public int kthSmallest(int[][] mat, int k) {
        List<Integer> list = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (i == 0) {
                    list.add(mat[i][j]);
                } else {
                    for (Integer integer : list) {
                        curr.add(mat[i][j] + integer);
                    }
                }
            }
            if(i==0){
                Collections.sort(list);
                if (list.size() > k) {
                    int size = list.size();
                    for(int temp=k;temp<size;temp++){
                        list.remove(k);
                    }
                }
                continue;
            }
            Collections.sort(curr);
            list.clear();
            if (curr.size() < k) {
                for (Integer integer : curr) {
                    list.add(integer);
                }
            }
            else {
                for (int l = 0; l < k; l++) {
                    list.add(curr.get(l));
                }
            }
            curr.clear();
        }
        return list.get(k-1);
    }
}

2.堆

• 创建优先级队列使用堆PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
• 堆中保存一个大小为3的数组，分别保存1️⃣ 当前数组和、2️⃣当前第i+1行数组num1的元素的索引下标、3️⃣前i行数组和num2的元素的索引下标。整个优先级队列的比较器按照当前数组和进行排序。
• 因为num1和num2都是有序的，因此num1[j]和num2[k]取过之后，下一个最小值只可能在1️⃣num1[j+1]+num2[k]、2️⃣num1[j]+num2[k+1]、以及3️⃣队列中剩余元素三者之间诞生。因此这就是为什么优先队列中存储的元素还需要包含索引下标。