文章目录
1252. 奇数值单元格的数目：
给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。
另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。
对 indices[i] 所指向的每个位置，应同时执行下述增量操作：
- ri 行上的所有单元格，加 1 。
- ci 列上的所有单元格，加 1 。
给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。
样例 1：
输入：
m = 2, n = 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 个奇数。
样例 2：
输入：
m = 2, n = 2, indices = [[1,1],[0,0]]
输出：
0
解释：
最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。
提示：
- 1 <= m, n <= 50
- 1 <= indices.length <= 100
- 0 <= ri < m
- 0 <= ci < n
进阶：
- 你可以设计一个时间复杂度为
O(n + m + indices.length)且仅用O(n + m)额外空间的算法来解决此问题吗？
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 如果直接模拟很容易就能做出题目，但是时间复杂度和空间复杂度都很高。
- 题目并没有要求输出最终的矩阵，而仅仅需要一个数目，那么是否可以减少空间呢？
- 试想，矩阵中某一个单元格的翻转次数就是所在行的操作次数加上所在列的操作次数，所以我们可以仅仅统计每一行翻转了几次，以及每一列翻转了几次，这样空间复杂度就降下来了，然后对行和列的翻转计数进行双层循环（对于一个单元格，只有当行和列的翻转次数，一个为偶数，一个为奇数，最终的翻转次数才会是奇数），这样时间复杂度也会大幅降低，但是距离进阶的要求还有距离。
- 事实上，我们不需要知道具体哪个单元格的翻转次数是奇数，我们只需要计数，所以我们只需要看翻转次数为奇数和偶数的行分别是多少，以及翻转次数为奇数和偶数的列分别是多少，就可以计算出最终有多少个翻转奇数次的单元格。
题解
rust
impl Solution {
pub fn odd_cells(m: i32, n: i32, indices: Vec<Vec<i32>>) -> i32 {
let mut rOdd = vec![false; m as usize];
let mut cOdd = vec![false; n as usize];
let mut rOddCnt = 0;
let mut cOddCnt = 0;
indices.iter().for_each(|i| {
if rOdd[i[0] as usize] {
rOdd[i[0] as usize] = false;
rOddCnt -= 1
} else {
rOdd[i[0] as usize] = true;
rOddCnt += 1
}
if cOdd[i[1] as usize] {
cOdd[i[1] as usize] = false;
cOddCnt -= 1;
} else {
cOdd[i[1] as usize] = true;
cOddCnt += 1;
}
});
let rEvenCnt = m - rOddCnt;
let cEvenCnt = n - cOddCnt;
return rOddCnt * cEvenCnt + cOddCnt * rEvenCnt;
}
}
go
func oddCells(m int, n int, indices [][]int) int {
rOdd := make([]bool, m)
cOdd := make([]bool, n)
rOddCnt := 0
cOddCnt := 0
for _, i := range indices {
if rOdd[i[0]] {
rOdd[i[0]] = false
rOddCnt--
} else {
rOdd[i[0]] = true
rOddCnt++
}
if cOdd[i[1]] {
cOdd[i[1]] = false
cOddCnt--
} else {
cOdd[i[1]] = true
cOddCnt++
}
}
rEvenCnt := m - rOddCnt
cEvenCnt := n - cOddCnt
return rOddCnt*cEvenCnt + cOddCnt*rEvenCnt
}
typescript
function oddCells(m: number, n: number, indices: number[][]): number {
const rOdd = new Array(m);
const cOdd = new Array(n);
let rOddCnt = 0;
let cOddCnt = 0;
for (const i of indices) {
if (rOdd[i[0]]) {
rOdd[i[0]] = false;
--rOddCnt;
} else {
rOdd[i[0]] = true;
++rOddCnt;
}
if (cOdd[i[1]]) {
cOdd[i[1]] = false;
--cOddCnt;
} else {
cOdd[i[1]] = true;
++cOddCnt;
}
}
const rEvenCnt = m - rOddCnt;
const cEvenCnt = n - cOddCnt;
return rOddCnt * cEvenCnt + cOddCnt * rEvenCnt;
};
python
class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
r_odd = [False] * m
c_odd = [False] * n
r_odd_cnt = 0
c_odd_cnt = 0
for i in indices:
if r_odd[i[0]]:
r_odd[i[0]] = False
r_odd_cnt -= 1
else:
r_odd[i[0]] = True
r_odd_cnt += 1
if c_odd[i[1]]:
c_odd[i[1]] = False
c_odd_cnt -= 1
else:
c_odd[i[1]] = True
c_odd_cnt += 1
r_even_cnt = m - r_odd_cnt
c_even_cnt = n - c_odd_cnt
return r_odd_cnt * c_even_cnt + c_odd_cnt * r_even_cnt
c
int oddCells(int m, int n, int** indices, int indicesSize, int* indicesColSize){
bool rOdd[m];
memset(rOdd, false, sizeof(rOdd));
bool cOdd[n];
memset(cOdd, false, sizeof(cOdd));
int rOddCnt = 0;
int cOddCnt = 0;
for (int i = 0; i < indicesSize; ++i) {
int *ind = indices[i];
if (rOdd[ind[0]]) {
rOdd[ind[0]] = false;
--rOddCnt;
} else {
rOdd[ind[0]] = true;
++rOddCnt;
}
if (cOdd[ind[1]]) {
cOdd[ind[1]] = false;
--cOddCnt;
} else {
cOdd[ind[1]] = true;
++cOddCnt;
}
}
int rEvenCnt = m - rOddCnt;
int cEvenCnt = n - cOddCnt;
return rOddCnt * cEvenCnt + cOddCnt * rEvenCnt;
}
c++
class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& indices) {
bool rOdd[m];
memset(rOdd, false, sizeof(rOdd));
bool cOdd[n];
memset(cOdd, false, sizeof(cOdd));
int rOddCnt = 0;
int cOddCnt = 0;
for (vector<int> &i: indices) {
if (rOdd[i[0]]) {
rOdd[i[0]] = false;
--rOddCnt;
} else {
rOdd[i[0]] = true;
++rOddCnt;
}
if (cOdd[i[1]]) {
cOdd[i[1]] = false;
--cOddCnt;
} else {
cOdd[i[1]] = true;
++cOddCnt;
}
}
int rEvenCnt = m - rOddCnt;
int cEvenCnt = n - cOddCnt;
return rOddCnt * cEvenCnt + cOddCnt * rEvenCnt;
}
};
java
class Solution {
public int oddCells(int m, int n, int[][] indices) {
boolean rOdd[] = new boolean[m];
boolean cOdd[] = new boolean[n];
int rOddCnt = 0;
int cOddCnt = 0;
for (int[] i : indices) {
if (rOdd[i[0]]) {
rOdd[i[0]] = false;
--rOddCnt;
} else {
rOdd[i[0]] = true;
++rOddCnt;
}
if (cOdd[i[1]]) {
cOdd[i[1]] = false;
--cOddCnt;
} else {
cOdd[i[1]] = true;
++cOddCnt;
}
}
int rEvenCnt = m - rOddCnt;
int cEvenCnt = n - cOddCnt;
return rOddCnt * cEvenCnt + cOddCnt * rEvenCnt;
}
}
原题传送门：https://leetcode.cn/problems/cells-with-odd-values-in-a-matrix/
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
本文含有隐藏内容，请 开通VIP 后查看