题目描述

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

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

样例

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

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

输入：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 。 

输入：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] 是一个非递减数组

算法分析

• 1、先算出第一行的前k小，再算出第一行和第二行只挑一个的前k小，再算出第一行，二行，三行只挑一个的前k小....
• 2、last存的是枚举到上一行前k小的值
• 3、next存的是当前行i的所有元素和last中所有元素的搭配后的所有值，对next进行排序，清空last，将前k小放last中
• 4、枚举完所有行后，last的最后一个元素即第k小的值

时间复杂度 $O(n(mk + log(mk))$

Java 代码

class Solution {
    public int kthSmallest(int[][] mat, int k) {
        int n = mat.length;
        int m = mat[0].length;

        ArrayList<Integer> last = new ArrayList<Integer>();
        last.add(0);
        for(int i = 0;i < n;i ++)
        {
            ArrayList<Integer> next = new ArrayList<Integer>();
            for(int j = 0;j < m;j ++)
            {
                for(int u : last)
                {
                    next.add(mat[i][j] + u);
                }
            }
            Collections.sort(next);
            last.clear();
            for(int j = 0;j < k && j < next.size();j ++)
            {
                last.add(next.get(j));
            }
        }
        return last.get(k - 1);
    }
}