题目地址:https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/submissions/
给你一个大小为m n的矩阵mat,矩阵由若干军人和平民组成,分别用 1 和 0 表示。 请你返回矩阵中战斗力最弱的k行的索引,按从最弱到最强排序。 如果第i行的军人数量少于第j行,或者两行军人数量相同但 i 小于 j,那么我们认为第 i 行的战斗力比第 j 行弱。 军人 总是 排在一行中的靠前位置,也就是说 1 总是出现在 0 之前。 https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/submissions/
示例 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] https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/submissions/
示例 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-cn.com/problems/the-k-weakest-rows-in-a-matrix/submissions/
看题目,意思大概就是,传入一个二维数组,以行统计战斗力,1为士兵为1战斗力,0为农民没有战斗力,且一行中有序,意味着碰到0就说明后面都是0
一、爆破法
先用一个数组,一个下标记录了每一行的战斗力,再通过循环遍历刚刚的战斗力数组的形式,将答案记录在返回的ans数组里面,因为考虑到防止重复读取同一个元素,但是又不想做排除和排序,所以想到了直接将记录过的数组元素设置为int的最大值,这样可以防止再次使用。
执行结果如下:
52 / 52 个通过测试用例
状态:通过
执行用时: 1 ms
内存消耗: 39.5 MB
public static int[] kWeakestRowsMe(int[][] mat, int k) {
int[] arr = new int[mat.length];
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[i].length; j++) {
if (0 == mat[i][j]) break;
arr[i]++;
}
}
int min = Integer.MAX_VALUE;
int minIndex = -1;
int[] ans = new int[k];
for (int i = 0; i < k; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
ans[i] = minIndex;
arr[minIndex] = Integer.MAX_VALUE;
min = Integer.MAX_VALUE;
}
return ans;
}
看了一下,官方用的都是比我还爆破的爆破,然后评论区里双百的答案时间比我长内存比我大(可能是那个时候刷的人少?)
总的来说我知道我这题一定不是最优解,但是评论区没有内存和时间上比我这个更好的(我的是1ms和39.5,基本很少有38的)
所以这道题只提供我自己的爆破法。
如果有需要可以到题目地址:https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/solution/,去看看评论区(java的回答比较少)