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 的数量最多（2）。所以返回下标 1 和数量 2。所以答案是 [1,2]。

示例 3：

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

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • mat[i][j] 不是 0 就是 1

解题思路

这是一道简单的矩阵遍历题目。我们需要统计每一行中 1 的个数，找出数量最多的那一行。

思路分析

方法：逐行统计

  • 遍历矩阵的每一行，统计当前行中 1 的个数
  • 维护当前找到的最大 1 的个数和对应的行下标
  • 当发现更多 1 的行时，更新最大值和行下标
  • 由于题目要求在数量相同时选择下标最小的行，我们只在严格大于当前最大值时才更新

具体步骤：

  1. 初始化最大 1 的个数为 0，最佳行下标为 0
  2. 遍历每一行，使用内层循环或内置函数统计当前行的 1 的个数
  3. 如果当前行的 1 的个数严格大于已知的最大个数，更新最大个数和行下标
  4. 返回最佳行下标和最大个数

时间复杂度为 O(m×n)，其中 m 是行数，n 是列数。空间复杂度为 O(1)，只使用常数额外空间。

这种方法简单直接，代码易读，适合这道简单题目的要求。

代码实现

class Solution {
public:
    vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
        int maxOnes = 0;
        int maxRow = 0;
        
        for (int i = 0; i < mat.size(); i++) {
            int ones = 0;
            for (int j = 0; j < mat[i].size(); j++) {
                ones += mat[i][j];
            }
            if (ones > maxOnes) {
                maxOnes = ones;
                maxRow = i;
            }
        }
        
        return {maxRow, maxOnes};
    }
};

class Solution:
    def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
        max_ones = 0
        max_row = 0
        
        for i in range(len(mat)):
            ones = sum(mat[i])
            if ones > max_ones:
                max_ones = ones
                max_row = i
        
        return [max_row, max_ones]

public class Solution {
    public int[] RowAndMaximumOnes(int[][] mat) {
        int maxOnes = 0;
        int maxRow = 0;
        
        for (int i = 0; i < mat.Length; i++) {
            int ones = 0;
            for (int j = 0; j < mat[i].Length; j++) {
                ones += mat[i][j];
            }
            if (ones > maxOnes) {
                maxOnes = ones;
                maxRow = i;
            }
        }
        
        return new int[] {maxRow, maxOnes};
    }
}

var rowAndMaximumOnes = function(mat) {
    let maxOnes = 0;
    let maxRow = 0;
    
    for (let i = 0; i < mat.length; i++) {
        const ones = mat[i].reduce((sum, val) => sum + val, 0);
        if (ones > maxOnes) {
            maxOnes = ones;
            maxRow = i;
        }
    }
    
    return [maxRow, maxOnes];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历矩阵中的每个元素，其中 m 是行数，n 是列数
空间复杂度O(1)只使用常数额外空间存储最大值和行下标