https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/
Given
n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.
Return the number of cells with odd values in the matrix after applying the increment to all
indices.
Example 1:
Input: n = 2, m = 3, indices = [[0,1],[1,1]] Output: 6 Explanation: Initial matrix = [[0,0,0],[0,0,0]]. After applying first increment it becomes [[1,2,1],[0,1,0]]. The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.
Example 2:
Input: n = 2, m = 2, indices = [[1,1],[0,0]] Output: 0 Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.
Solution 2: Counting
For each row and column, compute how many times it will be increased (odd or even).
For each a[i][j], check how many times the i-th row and j-th column were increased, if the sum is odd then a[i][j] will odd.
Time complexity: O(n*m + k)
Space complexity: O(n+m)
int oddCells(int n, int m, vector<vector<int>>& indices) {
vector<int> cols(m);
vector<int> rows(n);
for (const auto& idx : indices) {
rows[idx[0]] ^= 1;
cols[idx[1]] ^= 1;
}
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
ans += rows[i] ^ cols[j];
return ans;
}
(数学，哈希表)
- 暴力的做法很简单，直接模拟即可。这里我们假设
n和m都给到了 ，indices.length即L给到了 。 - 分析哪些单元格最后会变成奇数。我们按行来看，假设这一行有过奇数次更新，则这一行中经过偶数次更新的列可以成为奇数；如果这一行经过偶数次更新，则这一行中经过奇数次更新的列可以成为奇数。
- 我们如果统计出了有多少行经过了奇数次更新
cnt_r，以及有多少列经过了奇数次更新cnt_c，则答案就是cnt_r * (m - cnt_c) + cnt_c * (n - cnt_r)。 - 统计以上信息可以用一个哈希表来记录。
时间复杂度
- 由于哈希表的时间复杂度是常数，我们只遍历一次
indices数组即可完成统计。 - 故总时间复杂度为 。
空间复杂度
- 由于需要存储哈希表，而哈希表的大小与 L 线性相关，故空间复杂度为 。
int oddCells(int n, int m, vector<vector<int>>& indices) {
unordered_map<int, int> r, c;
int cnt_r = 0, cnt_c = 0;
for (const auto &v : indices) {
int &vr = r[v[0]], &vc = c[v[1]];
vr ^= 1; vc ^= 1;
cnt_r += (vr & 1) ? 1 : -1;
cnt_c += (vc & 1) ? 1 : -1;
}
return cnt_r * (m - cnt_c) + cnt_c * (n - cnt_r);
}
Solution 1: Simulation
Time complexity: O((n+m)*k + n*m)
Space complexity: O(n*m)
int oddCells(int n, int m, vector<vector<int>>& indices) {
vector<vector<int>> a(n, vector<int>(m));
for (const auto& idx : indices) {
for (int x = 0; x < m; ++x) ++a[idx[0]][x];
for (int y = 0; y < n; ++y) ++a[y][idx[1]];
}
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
ans += a[i][j] & 1;
return ans;
}
时间复杂度：O(L*(n + m) + n * m)
空间复杂度：O(n * m)
1 int oddCells(int n, int m, vector<vector<int>>& indices) { 2 int cnt = 0; 3 vector<vector<int> > matrix(n, vector<int>(m, 0)); 4 for (int i = 0; i < indices.size(); ++i) { 5 int r = indices[i][0], c = indices[i][1]; 6 for (int j = 0; j < m; ++j) { 7 matrix[r][j] += 1; 8 } 9 for (int k = 0; k < n; ++k) { 10 matrix[k][c] += 1; 11 } 12 } 13 for (int i = 0; i < n; ++i) { 14 for (int j = 0; j < m; ++j) { 15 if ((matrix[i][j] & 1) == 1) 16 ++cnt; 17 } 18 } 19 return cnt; 20 }
首先遍历indices，计算出每行每列分别做了几次+1的操作。然后再遍历matrix，根据matrix[i][j]求得对应的i行和j列分别做了几次+1，判断两者之和的奇偶性即可。
def oddCells(self, n, m, indices): """ :type n: int :type m: int :type indices: List[List[int]] :rtype: int """ dic_row = {} dic_column = {} for (r,c) in indices: dic_row[r] = dic_row.setdefault(r,0) + 1 dic_column[c] = dic_column.setdefault(c, 0) + 1 res = 0 for i in range(n): for j in range(m): count = dic_row.get(i,0) + dic_column.get(j,0) if count % 2 == 1:res += 1 return res
思路二：我们判断矩阵（i，j)位置的奇偶性，只需要计算第i行加1的次数 + 第j列加1的次数，就是位置（i， j）的值，只需要判断它的奇偶性就行。进一步，我们只需要知道第i行加1的总次数的奇偶性，以及第j列加1的总次数的奇偶性，这两个数进行异或操作就行（同奇同偶，加起来肯定是偶数，异或结果为0,否则为1）
时间复杂度：O(L + n * m)
空间复杂度：O(n + m)
1 int oddCells(int n, int m, vector<vector<int>>& indices) { 2 int cnt = 0; 3 vector<int> row(n, 0), col(m, 0); //row(i)表示加1次数的值的奇偶性，0为偶数次，1为奇数次 4 for (auto ind: indices) { 5 int r = ind[0], c = ind[1]; 6 row[r] ^= 1; 7 col[c] ^= 1; 8 } 9 for (int i = 0; i < n; ++i) { 10 for (int j = 0; j < m; ++j) { 11 if (row[i] ^ col[j]) 12 ++cnt; 13 } 14 } 15 return cnt; 16 }
思路三：基于思路二，我们发现判断（i， j）位置的值是否为奇数，只用看row(i) ^ col(j), 如果(i, j)位置的数为奇数，则row(i)或者col(j)必有一个是奇数， 如果两个都是奇数，那么为偶数。
时间复杂度：O(L + n + m)
空间复杂度：O(n + m)
1 int oddCells(int n, int m, vector<vector<int>>& indices) { 2 int cnt = 0; 3 vector<int> row(n, 0), col(m, 0); //row(i)表示加1次数的值的奇偶性，0为偶数次，1为奇数次 4 for (auto ind: indices) { 5 int r = ind[0], c = ind[1]; 6 row[r] ^= 1; 7 col[c] ^= 1; 8 } 9 int cntRow = 0, cntCol = 0; 10 for (auto i:row) 11 cntRow += i; 12 for (auto i:col) 13 cntCol += i; 14 return m * cntRow + n * cntCol - 2 * cntRow * cntCol; 15 }
时间复杂度：O(L)
空间复杂度：O(n + m)
1 int oddCells(int n, int m, vector<vector<int>>& indices) { 2 int cntRow = 0, cntCol = 0; 3 vector<int> row(n, 0), col(m, 0); //row(i)表示加1次数的值的奇偶性，0为偶数次，1为奇数次 4 for (auto ind: indices) { 5 int r = ind[0], c = ind[1]; 6 row[r] ^= 1; 7 col[c] ^= 1; 8 cntRow += (row[r] == 1) ? 1 : -1; 9 cntCol += (col[c] == 1) ? 1 : -1; 10 } 11 return m * cntRow + n * cntCol - 2 * cntRow * cntCol; 12 }
