一、题目
1. 描述
给你一个大小为 m × n m \times n m×n 的矩阵 mat,矩阵由若干军人和平民组成,分别用 1 1 1 和 0 0 0 表示。请你返回矩阵中战斗力最弱的 k k k 行的索引,按从最弱到最强排序。如果第 i i i 行的军人数量少于第 j j j 行,或者两行军人数量相同但 i i i 小于 j j j,那么我们认为第 i 行的战斗力比第 j 行弱。军人总是排在一行中的靠前位置,也就是说 1 1 1 总是出现在 0 0 0 之前。
2. 示例
- 示例一
输入: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]
- 示例二
输入: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]
二、解题
1. 思路
- 需要每行的能量的和:求和函数
- 将每行的能量和进行比较(排序),同时需要记录这些能量和的下标:用哈希表实现,key(行数),value(行的能量和)。
- 难点:哈希表按照值排序。
2.代码
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
int n = mat.length;
int i =0;
for(int[] ma:mat){
map.put(i++,getSum(ma));
}
//HashMap按照值排序
//创建HashMap的键list,根据值将list中的键排序,用排好序的键去搜索HashMap。
List<Integer> list = new ArrayList<Integer>(map.keySet());
Collections.sort(list, (a,b) -> map.get(a)-map.get(b));
System.out.print(list.size());
int[] ans = new int[k];
for(int j=0;j<k;j++){
ans[j] = list.get(j);
}
return ans;
}
public int getSum(int[] nums){
int sum=0;
for(int num: nums){
sum+=num;
}
return sum;
}
}