题目大意：
有序矩阵中的第 k 个最小数组和
给你一个 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] 是一个非递减数组
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1439
解题思路分析：
- 试想，如果矩阵只有一行的话，那么最小的k个数组（数字），一定是这一行的前k个数字。
- 当数组有2行的时候，前k小的数组一定是在第一行的前k个数字与第二行的所有数字组成的所有数组中产生，所以我们需要两层循环，第一层循环是前一行的k个数字，第二层循环是第二层的所有数字，他们俩俩相加后，和为前k小的数组为当前解。
- 当数组有3行的时候，同理2行的情况，前k小的数组一定是从前两行和为前k小的数组与第三行所有数字组成的数组中产生。因此我们同样使用两层循环，计算出前k小数组的和。
- 以此类推，直到计算完所有行。
解题时，我们使用PriorityQueue来记录当前行最小的k个数字，然后使用这k个数字与下一行的所有数字俩俩组合相加，结果中最小的k个和替代queue中的k个数字，继续与下一行进行计算即可。
实现代码：
public int kthSmallest(int[][] mat, int k) {
// 第一行前k小的数字
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
for(int i=0;i<mat[0].length;i++){
if(q.size()<k) q.offer(mat[0][i]);
else break;
}
// 从第2行向后循环
for(int r=1;r<mat.length;r++){
// 当前行为止能组成的前k小的数组和
PriorityQueue<Integer> nq = new PriorityQueue<>((a,b)->b-a);
// 循环queue中每个数字
while(q.size()>0){
int n=q.poll(); // 取出一个数字
// 循环当前行每个数字
for(int c=0;c<mat[0].length;c++){
if(nq.size()<k){ // 如果nq元素个数小于k
nq.offer(n+mat[r][c]); // 将当前列与n的和加入
}
// 如果nq中元素个数等于k，并且当前列与n的和小于nq中最大值
else if(n+mat[r][c]<nq.peek()){
// 将当前列与n的和加入
nq.offer(n+mat[r][c]);
// 取出nq中最大值
// 保证nq中是前k小的数字
nq.poll();
}else break;
}
}
q=nq;
}
return q.poll();
}本题解法执行时间99ms。
Runtime: 99 ms, faster than 60.00% of Java online submissions for Find the Kth Smallest Sum of a Matrix With Sorted Rows.
Memory Usage: 47.4 MB, less than 100.00% of Java online submissions for Find the Kth Smallest Sum of a Matrix With Sorted Rows.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1439-find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows-解题思路分析/