题目

给你一个大小为 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

思路

二分查找找到每一行1的个数

解法

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < mat.length; i++){
            //二分查找找到每一行1的个数
            int left = 0, right = mat[i].length - 1, temp = 0;
            while(left <= right){
                int mid = (left + right) / 2;
                if(mat[i][mid] != 0){
                    left = mid + 1;
                    temp = mid + 1;
                }else right = mid - 1;
            }
            map.put(i,temp);  //map存储第i行1的个数为temp
        }

        //按着hashmap中value的大小排序
        List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                int compare = (o1.getValue()).compareTo(o2.getValue());
                return compare;
            }
        });
        Map<Integer, Integer> returnMap = new LinkedHashMap<Integer, Integer>();
        for (Map.Entry<Integer, Integer> entry : list) {
            returnMap.put(entry.getKey(), entry.getValue());
        }

        //map中key依次放入list
        List<Integer> resList = new ArrayList<>();
        for (Integer key : returnMap.keySet()) {
            resList.add(key);
        }

        //list前k个元素放入数组
        int[] ans = new int[k];
        for(int i = 0; i < k; i++){
            ans[i] = resList.get(i);
        }
        return ans;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现