1252 Cells with Odd Values in a Matrix 奇數(shù)值單元格的數(shù)目
Description:
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:
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.
Constraints:
1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m
題目描述:
給你一個 n 行 m 列的矩陣，最開始的時候，每個單元格中的值都是 0。
另有一個索引數(shù)組 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分別表示指定的行和列（從 0 開始編號）。
你需要將每對 [ri, ci] 指定的行和列上的所有單元格的值加 1。
請你在執(zhí)行完所有 indices 指定的增量操作后，返回矩陣中 「奇數(shù)值單元格」 的數(shù)目。
示例 :
示例 1：
輸入：n = 2, m = 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 個奇數(shù)。
示例 2：
輸入：n = 2, m = 2, indices = [[1,1],[0,0]]
輸出：0
解釋：最后的矩陣是 [[2,2],[2,2]]，里面沒有奇數(shù)。
提示：
1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m
思路:
- 按照題目要求, 設置一個二維數(shù)組, 找到里面的奇數(shù)輸出即可
時間復雜度O(pq), 空間復雜度O(mn), 其中 p為 indices的長度, q為 max(m ,n) - 因為每次只用考慮行或者列, 可以只用一維數(shù)組記錄行和列的變化, 然后最后去掉交叉的部分(不清楚可以畫 venn圖)
時間復雜度O(p), 空間復雜度O(q), 其中 p為 indices的長度, q為 max(m ,n)
代碼:
C++:
class Solution
{
public:
int oddCells(int n, int m, vector<vector<int>>& indices)
{
vector<int> row(n), col(m);
for (auto indice : indices) row[indice[0]] ^= 1, col[indice[1]] ^= 1;
int r = accumulate(row.begin(), row.end(), 0), c = accumulate(col.begin(), col.end(), 0);
return r * m + c * n - 2 * r * c;
}
};
Java:
class Solution {
public int oddCells(int n, int m, int[][] indices) {
int row[] = new int[n], col[] = new int[m], result = 0;
for (int[] indice : indices) {
row[indice[0]] ^= 1;
col[indice[1]] ^= 1;
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (((row[i] + col[j]) & 1) == 1) ++result;
return result;
}
}
Python:
class Solution:
def oddCells(self, n: int, m: int, indices: List[List[int]]) -> int:
matrix = [[0 for _ in range(m)] for _ in range(n)]
for i, j in indices:
for col in range(m):
matrix[i][col] += 1
for row in range(n):
matrix[row][j] += 1
return sum(i & 1 for row in matrix for i in row)
