干货分享：奇数值单元格的数目（二）

解决方案

方法一：直接模拟思路和算法直接使用使用一个 n × m 的矩阵来存放操作的结果，对于 indices 中的每一对 [ ri , ci ] ，将矩阵第 ri 行的所有数增加 1 ，第 ci 列的所有数增加 1 。在所有操作模拟完毕后，我们遍历矩阵，得到奇数的数目。

代码

Python3

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

Java

class Solution { public int oddCells(int m, int n, int[][] indices) { int res = 0; int[][] matrix = new int[m][n]; for (int[] index : indices) { for (int i = 0; i < n; i++) { matrix[index[0]][i]++; } for (int i = 0; i < m; i++) { matrix[i][index[1]]++; } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if ((matrix[i][j] & 1) != 0) { res++; } } } return res; } }

C#

public class Solution { public int OddCells(int m, int n, int[][] indices) { int res = 0; int[,] matrix = new int[m, n]; foreach (int[] index in indices) { for (int i = 0; i < n; i++) { matrix[index[0], i]++; } for (int i = 0; i < m; i++) { matrix[i, index[1]]++; } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if ((matrix[i, j] & 1) != 0) { res++; } } } return res; } }

复杂度分析

时间复杂度：O(q×(m+n)+m×n) , 其中 q 表示数组 indices 的长度，m , n 为矩阵的行数与列数。遍历数组时，每次都需要更新矩阵中一行加一列，需要的时间为 O(q×(m+n)) ，最后还需要遍历矩阵，需要的时间为 O(m×n) ，总的时间复杂度为 O(q×(m+n)+m×n) 。

空间复杂度：O(m×n) ，其中 m , n 为矩阵的行数与列数。需要存储矩阵的所有元素。