题目大意：
方阵中战斗力最弱的 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.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1337-the-k-weakest-rows-in-a-matrix-解题思路分析/