Easy

题目描述

给定一个 m × n 的矩阵，初始时所有元素都为 0。还有一个二维数组 indices，其中 indices[i] = [ri, ci] 表示要在矩阵上执行增量操作的位置。

对于每个位置 indices[i]，执行以下两个操作：

  • 将第 ri 行的所有单元格加 1
  • 将第 ci 列的所有单元格加 1

给定 m、n 和 indices，返回在对 indices 中的所有位置执行增量操作后，矩阵中奇数值单元格的数量。

示例 1：

输入：m = 2, n = 3, indices = [[0,1],[1,1]]
输出：6
解释：初始矩阵 = [[0,0,0],[0,0,0]]。
应用第一次增量操作后变为 [[1,2,1],[0,1,0]]。
最终矩阵是 [[1,3,1],[1,3,1]]，包含 6 个奇数。

示例 2：

输入：m = 2, n = 2, indices = [[1,1],[0,0]]
输出：0
解释：最终矩阵 = [[2,2],[2,2]]。矩阵中没有奇数。

约束：

  • 1 <= m, n <= 50
  • 1 <= indices.length <= 100
  • 0 <= ri < m
  • 0 <= ci < n

解题思路

这道题有两种常见的解法：直接模拟和优化解法。

方法一：直接模拟 最直观的做法是创建 m×n 的矩阵，按照题目要求对每个 indices 进行操作，最后统计奇数个数。这种方法简单直接，但时间复杂度较高。

方法二：计数优化（推荐） 我们可以发现一个重要规律：矩阵中位置 (i, j) 的最终值等于第 i 行被操作的次数加上第 j 列被操作的次数。

具体思路：

  1. 用两个数组分别记录每行和每列被操作的次数
  2. 遍历 indices，统计每行每列的操作次数
  3. 对于矩阵中的每个位置 (i, j)，其值为 rowCount[i] + colCount[j]
  4. 如果这个和为奇数，则该位置为奇数

这种方法的时间复杂度为 O(indices.length + m×n)，空间复杂度为 O(m + n)，满足题目的进阶要求。

进一步优化：我们甚至不需要遍历整个矩阵，可以直接计算奇数个数。如果第 i 行被操作了奇数次，第 j 列被操作了偶数次（或相反），那么位置 (i, j) 就是奇数。

代码实现

class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<int> rowCount(m, 0);
        vector<int> colCount(n, 0);
        
        // 统计每行每列被操作的次数
        for (auto& idx : indices) {
            rowCount[idx[0]]++;
            colCount[idx[1]]++;
        }
        
        // 统计奇数次操作的行数和列数
        int oddRows = 0, oddCols = 0;
        for (int i = 0; i < m; i++) {
            if (rowCount[i] % 2 == 1) oddRows++;
        }
        for (int j = 0; j < n; j++) {
            if (colCount[j] % 2 == 1) oddCols++;
        }
        
        // 奇数个数 = 奇数行×偶数列 + 偶数行×奇数列
        return oddRows * (n - oddCols) + (m - oddRows) * oddCols;
    }
};

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        row_count = [0] * m
        col_count = [0] * n
        
        # 统计每行每列被操作的次数
        for r, c in indices:
            row_count[r] += 1
            col_count[c] += 1
        
        # 统计奇数次操作的行数和列数
        odd_rows = sum(count % 2 for count in row_count)
        odd_cols = sum(count % 2 for count in col_count)
        
        # 奇数个数 = 奇数行×偶数列 + 偶数行×奇数列
        return odd_rows * (n - odd_cols) + (m - odd_rows) * odd_cols

public class Solution {
    public int OddCells(int m, int n, int[][] indices) {
        int[] rowCount = new int[m];
        int[] colCount = new int[n];
        
        // 统计每行每列被操作的次数
        foreach (int[] idx in indices) {
            rowCount[idx[0]]++;
            colCount[idx[1]]++;
        }
        
        // 统计奇数次操作的行数和列数
        int oddRows = 0, oddCols = 0;
        for (int i = 0; i < m; i++) {
            if (rowCount[i] % 2 == 1) oddRows++;
        }
        for (int j = 0; j < n; j++) {
            if (colCount[j] % 2 == 1) oddCols++;
        }
        
        // 奇数个数 = 奇数行×偶数列 + 偶数行×奇数列
        return oddRows * (n - oddCols) + (m - oddRows) * oddCols;
    }
}

var oddCells = function(m, n, indices) {
    let rowCount = new Array(m).fill(0);
    let colCount = new Array(n).fill(0);
    
    for (let [r, c] of indices) {
        rowCount[r]++;
        colCount[c]++;
    }
    
    let oddRows = rowCount.filter(count => count % 2 === 1).length;
    let oddCols = colCount.filter(count => count % 2 === 1).length;
    
    return oddRows * (n - oddCols) + (m - oddRows) * oddCols;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(indices.length + m + n)遍历indices数组统计操作次数，然后遍历行列数组
空间复杂度O(m + n)需要额外的数组存储每行每列的操作次数