Given an array of numbers nums,in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1,2,1,3,5],return [3,5].
Answer:
假设要找的两个数为a,b。将数组中所有数异或得到a^b。因为a和b不同,所以a^b至少有一位为1。
假设第K位为1,构造一个第k位为1其他位为0的数和数组中所有数求与,来判断某数k位是否为1。
将k位为1的所有数进行异或,则得到a和b中的一个。另一个就简单了。
Code:
singleNumber(vector& nums) {
int ab = 0,a = 0,b = 0;
for(auto i:nums){
ab ^= i;
}
int check = ab & ~(ab-1);
for(auto i:nums){
if(i&check){
a ^= i;
}
}
b = ab ^ a;
vector res;
res.push_back(a);
res.push_back(b);
return res;
}
};