Given an array where all numbers appear in pairs except for two numbers, find those two numbers.
The single-number case is well known – just XOR everything. With two unique numbers, XOR gives a^b. Since a^b is non-zero, pick any bit position where it is 1, partition the array into two groups based on that bit, and XOR each group separately to get a and b.
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
| class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int ab = 0;
for (int i = 0; i < nums.size(); i++) {
ab ^= nums[i];
}
int pos = 0;
while(0 == ab % 2) {
pos++;
ab /= 2;
}
int a = 0;
int b = 0;
int tmp = (int)pow(2.0, pos);
for (int i = 0; i < nums.size(); i++) {
if ((nums[i]^tmp) == (nums[i] - tmp)) {
a ^= nums[i];
}
else {
b ^= nums[i];
}
}
vector<int> ans(0);
ans.push_back(a);
ans.push_back(b);
return ans;
}
};
|