How does the problem 'Cells with Odd Values in a Matrix' work?

In this problem, you increment specific rows and columns in a matrix and count how many cells have odd values afterward.

What is the primary pattern used in solving 'Cells with Odd Values in a Matrix'?

This problem is solved using the 'Array plus Math' pattern, as it requires efficient row and column manipulations combined with math for counting odd cells.

What are some common mistakes when solving 'Cells with Odd Values in a Matrix'?

Common mistakes include not optimizing the operations and performing inefficient matrix manipulations instead of simulating the changes.

How can I optimize my approach to solve 'Cells with Odd Values in a Matrix'?

Optimizing the solution involves tracking row and column operations instead of directly modifying the matrix. This helps reduce unnecessary computations.

What is the time complexity of solving 'Cells with Odd Values in a Matrix'?

The time complexity varies based on the approach. The optimized solution runs in O(m + n + k) time, where m and n are the matrix dimensions and k is the number of operations.

#1252

Easy

auto_awesome数组·数学

LeetCode 题解工作台

奇数值单元格的数目

给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0 。另有一个二维索引数组 indices ， indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。对 indices[i] 所指向的每个位置，应同…

数组数学模拟

题目描述

给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

对 indices[i] 所指向的每个位置，应同时执行下述增量操作：

r_i 行上的所有单元格，加 1 。
c_i 列上的所有单元格，加 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 <= r_i < m
0 <= c_i < n

进阶：你可以设计一个时间复杂度为 O(n + m + indices.length) 且仅用 O(n + m) 额外空间的算法来解决此问题吗？

lightbulb

解题思路

方法一：模拟

我们创建一个矩阵 $g$ 来存放操作的结果。对于 $\textit{indices}$ 中的每一对 $(r_i, c_i)$ ，我们将矩阵第 $r_i$ 行的所有数加 $1$ ，第 $c_i$ 列的所有元素加 $1$ 。

模拟结束后，遍历矩阵，统计奇数的个数。

时间复杂度 $O(k \times (m + n) + m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $k$ 为 $\textit{indices}$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        g = [[0] * n for _ in range(m)]
        for r, c in indices:
            for i in range(m):
                g[i][c] += 1
            for j in range(n):
                g[r][j] += 1
        return sum(v % 2 for row in g for v in row)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests understanding of matrix manipulation and array operations.
question_mark
Assesses ability to optimize solutions and recognize inefficiencies in naive approaches.
question_mark
Evaluates problem-solving skills in simulating operations and managing matrix states efficiently.

warning

常见陷阱

外企场景

error
Misunderstanding the task and applying increments directly to the matrix rather than simulating row/column operations.
error
Not accounting for the fact that multiple increments can affect the same row and column multiple times.
error
Failing to optimize the approach, leading to unnecessary computations and higher time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the matrix is much larger, and performance becomes an issue?
arrow_right_alt
How would the solution change if we had to also return the final matrix, not just the count of odd cells?
arrow_right_alt
What if the number of operations is significantly higher, affecting performance?

help

常见问题

外企场景

继续练习

#1806 还原排列的最少操作步数 #1823 找出游戏的获胜者 #2028 找出缺失的观测数据