LEETCODE 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows 解题思路分析

题目大意:

有序矩阵中的第 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。