2020-05-15 10:40:43

问题描述：

给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

示例 1：

输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。
示例 2：

输入：mat = [[1,3,11],[2,4,6]], k = 9
输出：17
示例 3：

输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。
示例 4：

输入：mat = [[1,1,10],[2,2,9]], k = 7
输出：12

提示：

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组

问题求解：

对于局部有序的数组可以使用优先队列在klogk的时间复杂度拿到topk，原因是由于局部有序，所以可以从小到大一次得到前k个数，这个和无序数组还是挺不同的，因为无序数组至少需要遍历一遍数组，所以时间复杂度是nlogk。

本题可以退化为leetcode 373，也就是两个数组的topk，然后依次去求即可。

    public int kthSmallest(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int[] res = mat[0];
        for (int i = 1; i < m; i++) {
            res = helper(res, mat[i]);
        }
        return res[k - 1];
    }
    
    private int[] helper(int[] nums1, int[] nums2) {
        List<Integer> temp = new ArrayList<>();
        int k = 200;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[0] + o1[1], o2[0] + o2[1]));
        int len1 = nums1.length;
        int len2 = nums2.length;
        for (int i = 0; i < len1; i++) pq.add(new int[]{nums1[i], nums2[0], 0});
        while (k-- > 0 && !pq.isEmpty()) {
            int[] curr = pq.poll();
            temp.add(curr[0] + curr[1]);
            if (curr[2] < len2 - 1) pq.add(new int[]{curr[0], nums2[curr[2] + 1], curr[2] + 1});
        }
        int[] res = new int[temp.size()];
        for (int i = 0; i < temp.size(); i++) res[i] = temp.get(i);
        return res;
    }