Description
给定一个数组\(nums[]\)，里面有2个数只出现一次，其它数只出现两次，找出前者
Constraints
要求\(O(n)\)时间复杂度，\(O(1)\)空间复杂度
Solution
二进制分组。设\(sum\)为xor之和，\(a, b\)为答案，由性质可知\(sum = a \oplus b\)
但是这个时候仍不足以区分答案。进一步发现\(sum\)里面必然有一个位设为1，以此作为二进制分组
划分为2组后就是低配版Single Number问题
Code
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int sum = 0;
for(auto n : nums) sum ^= n;
int pos;
for(auto p = 31; ~p; --p) {
if(sum >> p & 1) {
pos = p;
break;
}
}
vector<int> ab(2);
for(auto n : nums) {
ab[n >> pos & 1] ^= n;
}
return ab;
}
};