137. 只出现一次的数字 II

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

考点

  • 状态压缩
  • 排列组合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public:
		int singleNumber(vector<int>& nums) {
			int cntArr[32] = {0};
			for (auto &num : nums) {
				for (int i = 0; i < 32; i++) {
					if (num & (1U << i)) cntArr[i]++;
				}
			}
			int ans = 0;
			for (int i = 31; i >= 0; i--) {
				ans = (ans << 1) | (cntArr[i] % 3);
			}
			return ans;
		}
};

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

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

思路

根据题意除某个元素仅出现一次外，其余每个元素都恰出现三次，int类型的整数也都是32位

假设当前为第\(i\)位，\(Sum_i\)代表所有元素的第\(i\)位之和，\(r\)代表只出现了一次的元素在第\(i\)位的值，必满足以下等式 \[ Sum_i=3k+r \] 所以设置一个长度为32的cntArr数组，依次记录所有元素各在某位上的和

然后再遍历cntArr数组，对各个元素求余3后重新拼凑，即可得到只出现了一次的元素

比如有nums数组{2,2,2,14}，映射为二进制就是{0010,0010,0010,1110}

cntArr数组的值则应为{1,1,4,0}，求余3后为{1,1,1,0}，就等于只出现了一次的元素14的二进制表达