Easy

题目描述

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

解题思路

解题思路

这道题需要找到矩阵中战斗力最弱的 k 行。关键是理解战斗力的定义：军人数量少的行更弱，如果军人数量相同，则行号小的更弱。

方法一：直接统计 + 排序（推荐）

最直观的方法是统计每行的军人数量，然后按照题目要求排序。我们可以创建一个包含 (军人数量, 行索引) 的数组，利用排序的稳定性来处理相同军人数量的情况。

方法二：二分查找优化

由于军人总是排在前面（1 在 0 之前），我们可以用二分查找找到每行中第一个 0 的位置，从而快速确定军人数量。这在矩阵较大时会更高效。

方法三：最小堆

使用最小堆来维护最弱的 k 行，每次处理一行时将其信息加入堆中。这种方法在只需要前 k 个结果且 k 相对较小时比较有优势。

本题选择方法一作为主要解法，因为代码简洁易懂，且在给定的数据规模下（m,n ≤ 100）性能已经足够。

代码实现

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<pair<int, int>> rows;
        
        for (int i = 0; i < mat.size(); i++) {
            int soldiers = 0;
            for (int j = 0; j < mat[i].size(); j++) {
                soldiers += mat[i][j];
            }
            rows.push_back({soldiers, i});
        }
        
        sort(rows.begin(), rows.end());
        
        vector<int> result;
        for (int i = 0; i < k; i++) {
            result.push_back(rows[i].second);
        }
        
        return result;
    }
};

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        rows = []
        
        for i in range(len(mat)):
            soldiers = sum(mat[i])
            rows.append((soldiers, i))
        
        rows.sort()
        
        return [rows[i][1] for i in range(k)]

public class Solution {
    public int[] KWeakestRows(int[][] mat, int k) {
        var rows = new List<(int soldiers, int index)>();
        
        for (int i = 0; i < mat.Length; i++) {
            int soldiers = 0;
            for (int j = 0; j < mat[i].Length; j++) {
                soldiers += mat[i][j];
            }
            rows.Add((soldiers, i));
        }
        
        rows.Sort();
        
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = rows[i].index;
        }
        
        return result;
    }
}

var kWeakestRows = function(mat, k) {
    const rows = [];
    
    for (let i = 0; i < mat.length; i++) {
        const soldiers = mat[i].reduce((sum, val) => sum + val, 0);
        rows.push([soldiers, i]);
    }
    
    rows.sort((a, b) => {
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        }
        return a[1] - b[1];
    });
    
    return rows.slice(0, k).map(row => row[1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(m×n + m×log m)统计每行军人数量需要 O(m×n)，排序需要 O(m×log m)
空间复杂度O(m)存储每行的军人数量和索引信息