1252. 奇数值单元格的数目

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 957 阅读时长 ≈ 3 分钟

考点

  • 状态压缩
  • 排列组合

题解

同下

思路

已知二维数组M有m行，n列；indices数组有l个元素，且每个元素都是长度为2的一维数组

比如某元素值为[0,1]，代表二维数组中行序号为0的单元格先加一、列序号为1的单元格再加一

正常的暴力方式如下：

  1. 开辟m * n大小的二维数组空间

  2. 遍历indices数组每个元素的同时，每次分别按行、按列地对二维数组进行批量修改

    时间复杂度高达\(O\left( l\cdot \left( m+n \right) \right)\)

  3. 遍历二维数组的所有单元格，判断有多少个奇数

    时间复杂度\(O\left( m\cdot n \right)\)

组合拳下来，时间复杂度高达\(O\left( l\cdot \left( m+n \right) +\left( m\cdot n \right) \right)\)，空间复杂度高达\(O\left( m\cdot n \right)\)

空间优化

由于每次都是对某行或某列的所有单元格进行批量加1，可以做如下优化：

  • 设置一个长度为m的rows数组，下标映射为二维数组M的行序号，值映射为二维数组对应行的增量

  • 设置一个长度为n的cols数组，下标映射为二维数组M的列序号，值映射为二维数组对应列的增量

那么有： \[ M\left[ i \right] \left[ j \right] =rows\left[ i \right] +cols\left[ j \right] \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
	public:
		int oddCells(int m, int n, vector<vector<int>>& indices) {
			vector<int> rows(m, 0), cols(n, 0);
			for (auto &indice : indices) {
				rows[indice[0]]++;
				cols[indice[1]]++;
			}
			int ans = 0;
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if ((rows[i] + cols[j]) & 1) ans++;
				}
			}
			return ans;
		}
};

时间复杂度：\(O\left( l+m\cdot n \right)\)

空间复杂度：\(O\left( m+n \right)\)

计数优化 & 集合运算

根据数学性质，奇数 = 奇数 + 偶数

  • 假设有rows = {1,1}，cols = {0,2,0}

    从两个集合中各取任意一个元素，都可求和为奇数；可行的组合数为2 * 3 = 6

    意味着整个二维数组都是奇数，共有6个奇数

  • 假设有rows = {1,1,0}，cols = {1,0,1}

    rows取{1,1}时，cols取{0}才可为奇数，此时可行的组合数为2 * 1 = 2

    rows取{0}时，cols取{1,1}才可为奇数，此时可行的组合数为1 * 2 = 2

    意味着整个二维数组中，共有2 + 2 = 4个奇数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
	public:
		int oddCells(int m, int n, vector<vector<int>>& indices) {
			vector<int> rows(m, 0), cols(n, 0);
			for (auto &indice : indices) {
				rows[indice[0]]++;
				cols[indice[1]]++;
			}
			int rowOdd = 0, colOdd = 0;
			for (int i = 0; i < m; i++) {
				rowOdd += rows[i] & 1 ? 1 : 0;
			}
			for (int i = 0; i < n; i++) {
				colOdd += cols[i] & 1 ? 1 : 0;
			}
			return rowOdd * (n - colOdd) + (m - rowOdd) * colOdd;
		}
};

时间复杂度：\(O\left( l+m+n \right)\)

空间复杂度：\(O\left( m+n \right)\)

位运算 & 状态压缩 & 集合运算

题目限定了m与n均不超过50，使用两个long类型的变量来替代rows与cols数组

用比特位1代表增量为奇数，用比特位0代表增量为偶数

各统计两个变量的1个数，即各自拥有的奇数个数，再做上述的集合运算即可

bitCount实现请参见191. 位1的个数，不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
	private:
		int bitCount(long n) {
			//--------分治法--------
			n = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555);
			n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
			n = (n & 0x0f0f0f0f0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f0f0f0f0f);
			n = (n & 0x00ff00ff00ff00ff) + ((n >> 8) & 0x00ff00ff00ff00ff);
			n = (n & 0x0000ffff0000ffff) + ((n >> 16) & 0x0000ffff0000ffff);
			n = (n & 0x00000000ffffffff) + ((n >> 32) & 0x00000000ffffffff);
			return n;
			//--------分治法--------
			//--------Brian Kernighan法--------
//			int cnt = 0;
//			while (n) {
//				n &= n - 1;
//				cnt++;
//			}
//			return cnt;
			//--------Brian Kernighan法--------
			//--------lowBit--------
//			int cnt = 0;
//			while (n) {
//				n -= (n & -n);
//				cnt++;
//			}
//			return cnt;
			//--------lowBit--------
		}

	public:
		int oddCells(int m, int n, vector<vector<int>>& indices) {
			long rows = 0, cols = 0;
			for (auto &indice : indices) {
				rows ^= 1L << indice[0];
				cols ^= 1L << indice[1];
			}
			int rowOdd = bitCount(rows), colOdd = bitCount(cols);
			return rowOdd * (n - colOdd) + (m - rowOdd) * colOdd;
		}
};

时间复杂度：\(O\left( l+\log C \right)\)，这里\(C\)等于long的位数64

空间复杂度：\(O\left( 1 \right)\)