一最多的行

标签: 数组 矩阵

难度: Easy

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。

如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。

返回一个由行下标和该行中 1 的数量组成的数组。

示例 1：

输入：mat = [[0,1],[1,0]]
输出：[0,1]
解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。

示例 2：

输入：mat = [[0,0,0],[0,1,1]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

示例 3：

输入：mat = [[0,0],[1,1],[0,0]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

提示：

  • m == mat.length 
  • n == mat[i].length 
  • 1 <= m, n <= 100 
  • mat[i][j] 为 0 或 1

Submission

运行时间: 32 ms

内存: 16.5 MB

class Solution:
    def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
        # sumslist = []
        # for lst in mat:
        #     sumslist.append(sum(lst))
        # m = max(sumslist)
        # idx = sumslist.index(m)
        # return [idx, m]
        max_sum, idx = -1, 0
        for i, row in enumerate(mat):
            s = sum(row)
            if s > max_sum:
                max_sum, idx = s, i
        return [idx, max_sum]

Explain

题解的核心思想是遍历矩阵的每一行，计算每行中1的数量，同时跟踪记录最大1的数量及其对应的行索引。如果发现有行1的数量大于当前记录的最大数量，则更新最大数量和行索引。最后返回包含最大1数量的行的索引和1的数量。这种方法直接遍历矩阵，计算每行的1的总数，并实时更新最大值和对应的行索引。

时间复杂度: O(m * n)

空间复杂度: O(1)

class Solution:
    def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
        max_sum, idx = -1, 0  # 初始化最大1的数量为-1，索引为0
        for i, row in enumerate(mat):  # 遍历每一行
            s = sum(row)  # 计算当前行的1的数量
            if s > max_sum:  # 如果当前行的1的数量大于之前记录的最大数量
                max_sum, idx = s, i  # 更新最大数量和行索引
        return [idx, max_sum]  # 返回最大1数量的行索引和1的数量

Explore

这个算法选择遍历整个矩阵计算每一行的1的数量，主要是因为它不依赖于行中数据的排序状态。虽然二分查找在已排序的行中可以更快地找到1的数量，但这需要额外的条件：每行必须是排序的。对于未排序的行，二分查找将不适用。此外，二分查找虽然可以加速单行的查找过程，但整体上仍然需要遍历每一行，时间复杂度在最坏情况下仍然接近O(n*m)（n为行数，m为行的最大长度）。因此，直接遍历整个矩阵是一种更通用且在未排序数据中有效的方法。

当前算法假设矩阵的每一行长度相同，因此直接使用sum函数来计算每行1的数量。如果矩阵行的长度不同，算法本身不需要做根本性的更改，因为Python的sum函数可以正常处理不同长度的行。但是，为了保持代码的健壮性，可以在实现时添加一些检查，确保不同长度的行被正确处理，例如检查每一行的数据类型和结构是否符合预期。

在提供的代码实现中，当找到具有更多1的新行时，会更新最大1的数量及其对应的行索引。如果后续行的1数量与当前最大数量相同，算法不会更新行索引。因此，只有当找到的1数量严格大于当前记录的最大数量时，行索引才会更新。这确保了如果有多行具有相同的最大1数量，返回的是第一次达到该数量的行的索引，即最小的行索引。

当前算法对于稀疏矩阵（即大多数元素为0的矩阵）依然需要遍历所有元素，因此效率不是最优的。针对稀疏矩阵，可以考虑使用更适合稀疏数据的数据结构，如压缩行存储（Compressed Row Storage, CRS）或使用字典来记录每一行中1的位置，从而避免遍历大量的0。这样，计算每行中1的数量可以更加高效，因为只需要计算存储的非零元素数量。