矩阵中战斗力最弱的 K 行

难度: Easy

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

Submission

运行时间: 18 ms

内存: 16.4 MB

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        m, n = len(mat), len(mat[0])
        ans = [n - bisect_right(row[::-1], 0) for row in mat]
        idx = list(range(m))
        idx.sort(key=lambda i: ans[i])
        return idx[:k]

Explain

解题思路主要是利用二分查找来确定每一行中1的数量，并根据这个数量对行进行排序。首先，由于每一行的1总是在0之前，可以通过对每一行的逆序进行二分查找，找到0的位置，从而确定1的数量。然后，创建一个列表记录每一行的索引，按照每行1的数量进行排序。最后，返回排序后的前k个行索引。

时间复杂度: O(m log m)

空间复杂度: O(m)

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        m, n = len(mat), len(mat[0])
        # 计算每行中1的数量，使用二分查找
        ans = [n - bisect_right(row[::-1], 0) for row in mat]
        # 创建索引列表
        idx = list(range(m))
        # 根据每行1的数量排序索引
        idx.sort(key=lambda i: ans[i])
        # 返回战斗力最弱的k行的索引
        return idx[:k]

Explore

选择二分查找主要是因为每一行的1和0是分段的（所有的1都在0之前）。这种有序性使得二分查找非常合适，因为二分查找的时间复杂度为O(log n)，远低于直接遍历的O(n)。对于大规模数据，这种优化可以显著提高效率。

对每一行逆序再使用二分查找搜索0的原因是因为Python的标准库中的bisect模块可以很方便地找到一个元素应该插入有序列表的位置，从而确定目标元素的位置。由于1在0之前，逆序后我们可以更直接地使用bisect_right查找0的位置，从而确定1的数量。

在题解中，行索引是先按照1的数量排序的，如果1的数量相同，则自然按照列表中的初始顺序（即行的原始索引）作为第二排序关键字，这确保了当两行1的数量相同时，行索引较小的排在前面。这是因为sort函数在Python中是稳定的排序算法，即它会保持相等元素的相对顺序。

题解中的方法在大尺寸矩阵仍然有效，但效率可能会受到影响。优化方法可以包括：1) 使用并行处理来同时计算多行中1的数量。2) 如果1的分布非常稀疏或非常密集，可以考虑使用更具体的算法来减少不必要的查找。3) 可以使用更加高效的数据结构来存储矩阵，例如稀疏矩阵表示法，减少存储和计算的开销。4) 在一些特定的硬件上，比如使用GPU进行加速计算。