脚撕LeetCode(1337)Easy

题目地址：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的回答比较少）