LeetCode 1337. 矩阵中战斗力最弱的 K 行

一、题目

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;
    }
}

结果

LeetCode 1337. 矩阵中战斗力最弱的 K 行

上一篇:矩阵优化


下一篇:leetcode 1337. 矩阵中战斗力最弱的 K 行