奇数值单元格的数目

难度: Easy

给你一个 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) 额外空间的算法来解决此问题吗？

Submission

运行时间: 26 ms

内存: 16.1 MB

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        res = 0
        M = [   [0 for j in range(n) ] for i in range(m) ]
        for i in indices:
            for c in range(n):
                M[i[0]][c]+=1

            for r in range(m):
                M[r][i[1]]+=1
        for r in range(len(M)):
            for c in range(len(M[0])):
                if M[r][c]%2:
                    res +=1 
        return res

Explain

首先，初始化一个 m x n 的矩阵 M，所有元素初始值为 0。针对给定的 indices 数组，每个 [ri, ci] 表示一次操作，即将第 ri 行的所有元素值加 1，和将第 ci 列的所有元素值加 1。操作完成后，遍历整个矩阵 M，统计奇数值单元格的数量并返回这个计数。

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

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

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        res = 0  # 用于记录奇数单元格的数量
        # 初始化 m x n 的矩阵，所有元素为 0
        M = [[0 for _ in range(n)] for _ in range(m)]
        # 对每个指定的 [ri, ci] 执行行列增加操作
        for ri, ci in indices:
            for c in range(n):  # 增加整行
                M[ri][c] += 1
            for r in range(m):  # 增加整列
                M[r][ci] += 1
        # 遍历矩阵，统计奇数值单元格
        for r in range(m):
            for c in range(n):
                if M[r][c] % 2:
                    res += 1
        return res

Explore

在算法实现中，对每个指定的 [ri, ci] 操作，首先增加整个第 ri 行的值，然后增加整个第 ci 列的值。由于增加行值和列值是分开的两个步骤，所以位于 [ri][ci] 的单元格会被增加两次。这种处理是有意为之，以确保行和列的增加操作都被正确记录。最后，在计算奇偶性时，这种重复增加的效果将被正确处理，因为任何数值加2仍保持其原有的奇偶性。

在增加操作时直接统计奇数值的变化虽然看起来可以减少一次遍历的开销，但实际上由于每次操作可能影响多个单元格的奇偶性（一个操作会影响一整行和一整列），这会使得统计变得复杂且易出错。因此，为了保持算法的简洁性和正确性，选择在所有操作完成后通过一次完整的遍历来统计奇数单元格。这种方法虽然牺牲了一些效率，但极大地增强了代码的可读性和可维护性。

确实，当前的实现方法中，如果多次操作同一行或列，将会进行冗余计算。一种优化方法是使用两个数组，一个用于记录行的增加次数，另一个用于记录列的增加次数。最后，根据这两个数组计算每个单元格的最终值，并统计奇数单元格。这样做可以有效减少重复计算，提高算法效率。

如果indices数组为空，则不会执行任何增加操作，矩阵中所有元素保持初始值0，遍历统计时会返回0个奇数单元格。如果m或n为0，则初始化的矩阵维度为0，遍历操作本身不会执行，因此也会返回0个奇数单元格。因此，题解中的算法已经能够正确处理这些特殊情况。