每日一题——LeetCode1252.奇数值单元格的数目

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

方法一 直接模拟：

创建一个n x m的矩阵，初始化所有元素为0，对于indices中的每一对[ri,ci]，将矩阵第ri行的所有数增加1，第ci列的所有数增加1.最后遍历矩阵得到奇数的数目

var oddCells = function(m, n, indices) {let res = 0;const matrix = new Array(m).fill(0).map(() => new Array(n).fill(0));for (const index of indices) {for (let i = 0; i < n; i++) {matrix[index[0]][i]++;}for (let i = 0; i < m; i++) {matrix[i][index[1]]++;}}for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if ((matrix[i][j] & 1) !== 0) {res++;}}}return res;
};

消耗时间和内存情况：

 

方法二 模拟空间优化

用一个行数组 rows 和列数组 cols 分别记录每一行和每一列被增加的次数。

对于 indices中的每一对 [ri,ci]，我们将 rows[ri]和 cols[ci]的值分别增加 1。

位置 (x,y)位置的计数即为 rows[x]+cols[y]

遍历矩阵找出奇数的数目

var oddCells = function(m, n, indices) {const rows = new Array(m).fill(0);const cols = new Array(n).fill(0);for (const index of indices) {rows[index[0]]++;cols[index[1]]++;}let res = 0;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (((rows[i] + cols[j]) & 1) !== 0) {res++;}}}return res;
};

消耗时间和内存情况：

方法三 计数优化

见官方题解

作者：力扣官方题解
链接：1252.奇数值单元格的数目