LEETCODE 1337. The K Weakest Rows in a Matrix 解题思路分析

题目大意:

方阵中战斗力最弱的 K 行

给你一个大小为 m * n 的方阵 mat,方阵由若干军人和平民组成,分别用 1 和 0 表示。

请你返回方阵中战斗力最弱的 k 行的索引,按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行,或者两行军人数量相同但 i 小于 j,那么我们认为第 i 行的战斗力比第 j 行弱。

军人 总是 排在一行中的靠前位置,也就是说 1 总是出现在 0 之前。

示例 1:

输入:mat = 
 [[1,1,0,0,0],
  [1,1,1,1,0],
  [1,0,0,0,0],
  [1,1,0,0,0],
  [1,1,1,1,1]], 
 k = 3
输出:[2,0,3]
解释:
 每行中的军人数目:
 行 0 -> 2 
 行 1 -> 4 
 行 2 -> 1 
 行 3 -> 2 
 行 4 -> 5 
 从最弱到最强对这些行排序后得到 [2,0,3,1,4]

示例 2:

输入:mat = 
 [[1,0,0,0],
  [1,1,1,1],
  [1,0,0,0],
  [1,0,0,0]], 
 k = 2
输出:[0,2]
解释: 
 每行中的军人数目:
 行 0 -> 1 
 行 1 -> 4 
 行 2 -> 1 
 行 3 -> 1 
 从最弱到最强对这些行排序后得到 [0,2,3,1]

提示:

  • m == mat.length
  • n == mat[i].length
  • 2 <= n, m <= 100
  • 1 <= k <= m
  • matrix[i][j] 不是 0 就是 1

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1337

解题思路分析:

本题实际上是考察我们如何对矩阵中每一行数据进行排序,排序规则是优先军人数升序,军人数相同时行数升序排序。

解题时,我们遍历矩阵每一行,统计该行军人数量,将此数量以及行号插入到PriorityQueue中, PriorityQueue 中的数据顺序按照上文提到的排序规则来排序。然后再从Queue中取出前k个元素的行号即可。

实现代码:

public int[] kWeakestRows(int[][] mat, int k) {
    // 定义排序用的Queue
    // Queue中元素按照军人数升序,行号升序规则排序
    PriorityQueue<int[]> q
        = new PriorityQueue<>((a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
    // 循环矩阵每一行
    for(int r=0;r<mat.length;r++){
        // 统计该行军人数
        int count=0;
        for(int c=0;c<mat[0].length;c++){
            if(mat[r][c]==0) break;
            count++;
        }
        // 将该行军人数即行号存入Queue
        q.offer(new int[]{count, r});
    }
    // 从Queue中取出前k个元素的行号加入返回结果
    int[] res=new int[k];
    for(int i=0;i<k;i++){
        res[i]=q.poll()[1];
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 90.35% of Java online submissions for The K Weakest Rows in a Matrix.

Memory Usage: 41.9 MB, less than 100.00% of Java online submissions for The K Weakest Rows in a Matrix.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1337-the-k-weakest-rows-in-a-matrix-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

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