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

解决方法二模拟空间优化由于每次操作只会将一行和一列的数增加 1 因此我们可以使用一个行数组 rows 和列数组 cols 分别记录每一行和每一列被增加的次数。对于 indices 中的每一对 [ ri , ci ] 我们将 rows[ri] 和 cols[ci] 的值分别增加 1 。在所有操作完成后我们可以计算出位置 ( x , y ) 位置的计数即为 rows[x] cols[y] 。遍历矩阵即可得到所有奇数的数目。代码Python3class Solution: def oddCells(self, m: int, n: int, indices: List[List[int]]) - int: rows [0] * m cols [0] * n for x, y in indices: rows[x] 1 cols[y] 1 return sum((row col) % 2 for row in rows for col in cols)Javaclass Solution { public int oddCells(int m, int n, int[][] indices) { int[] rows new int[m]; int[] cols new int[n]; for (int[] index : indices) { rows[index[0]]; cols[index[1]]; } int res 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (((rows[i] cols[j]) 1) ! 0) { res; } } } return res; } }Cclass Solution { public: int oddCells(int m, int n, vectorvectorint indices) { vectorint rows(m), cols(n); for (auto index : indices) { rows[index[0]]; cols[index[1]]; } int res 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if ((rows[i] cols[j]) 1) { res; } } } return res; } };复杂度分析时间复杂度O(qm×n) , 其中 q 表示数组 indices 的长度m , n 为矩阵的行数与列数。遍历数组时需要的时间为 O(q) 最后还需要遍历矩阵需要的时间为 O(m×n) 因此总的时间复杂度为 O(qm×n) 。空间复杂度O(mn) 其中 m,n 为矩阵的行数与列数。需要存储矩阵的行数统计与列数统计。