260. 只出现一次的数字 III

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

考点

  • 状态压缩
  • 排列组合
  • 异或技巧

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
	public:
		vector<int> singleNumber(vector<int>& nums) {
            //这里使用long，避免计算lsb即最低有效位时溢出
			long xorSum = 0, lsb = 0;
			for (auto &num : nums) xorSum ^= num;
			//按最低有效位所在的比特位进行比较与分割
			int ans_1 = 0;
			lsb = (xorSum & (-xorSum));
			for (auto &num : nums) {
				if (num & lsb) ans_1 ^= num;
			}
			return vector<int> {ans_1, (int)(xorSum ^ ans_1)};
		}
};

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

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

思路

类似136. 只出现一次的数字，同样对数组的所有元素进行异或运算，得到xorSum；实际上就是最终两个答案的异或值，且必不为0

取xorSum任意一个值为1的比特位，记为i；其代表两个答案在i上不同，一个必为1一个必为0

根据在i上的值为0或1，将所有元素进行分组，两个答案必不在一个组；随后对每个组分别求异或和，即可得到两个答案

比如nums等于{1,1,2,2,3,5}，二进制表达为{001,001,010,010,011,101} ，xorSum为110

这里取i为010，即xorSum的最低有效位

与i作与运算为0的，子集合为{001,001,101}；与i作与运算为1的，子集合为{010,010,011}

任意取一个子集合作异或运算求和，即可得到其中一个答案；将这个答案与xorSum作异或运算，即可得到另一个答案