Question

2643. 一最多的行

English Version

题目描述

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

解法

方法一：模拟

我们直接遍历矩阵，统计每一行中 $1$ 的个数，更新最大值和对应的行下标。注意，如果当前行的 $1$ 的个数与最大值相等，我们需要选择行下标较小的那一行。

时间复杂度 $(m \times n)$，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。空间复杂度 $O(1)$。

class Solution:
  def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
    ans = [0, 0]
    for i, row in enumerate(mat):
      cnt = row.count(1)
      if ans[1] < cnt:
        ans = [i, cnt]
    return ans

class Solution {
  public int[] rowAndMaximumOnes(int[][] mat) {
    int[] ans = new int[2];
    for (int i = 0; i < mat.length; ++i) {
      int cnt = 0;
      for (int x : mat[i]) {
        if (x == 1) {
          ++cnt;
        }
      }
      if (ans[1] < cnt) {
        ans[0] = i;
        ans[1] = cnt;
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
    vector<int> ans(2);
    for (int i = 0; i < mat.size(); ++i) {
      int cnt = 0;
      for (auto& x : mat[i]) {
        cnt += x == 1;
      }
      if (ans[1] < cnt) {
        ans[0] = i;
        ans[1] = cnt;
      }
    }
    return ans;
  }
};

func rowAndMaximumOnes(mat [][]int) []int {
  ans := make([]int, 2)
  for i, row := range mat {
    cnt := 0
    for _, x := range row {
      if x == 1 {
        cnt++
      }
    }
    if ans[1] < cnt {
      ans[0], ans[1] = i, cnt
    }
  }
  return ans
}

function rowAndMaximumOnes(mat: number[][]): number[] {
  const ans: number[] = [0, 0];
  for (let i = 0; i < mat.length; ++i) {
    const cnt = mat[i].reduce((a, b) => a + b);
    if (ans[1] < cnt) {
      ans[0] = i;
      ans[1] = cnt;
    }
  }
  return ans;
}

impl Solution {
  pub fn row_and_maximum_ones(mat: Vec<Vec<i32>>) -> Vec<i32> {
    let mut ans = vec![0, 0];

    for (i, row) in mat.iter().enumerate() {
      let cnt = row
        .iter()
        .filter(|&v| *v == 1)
        .count() as i32;
      if ans[1] < cnt {
        ans[0] = i as i32;
        ans[1] = cnt;
      }
    }

    ans
  }
}