題目來源
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, 2, 5], return [3, 5].
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
找出數(shù)列中只出現(xiàn)一次的元素蟹倾，可以哈希神郊，但是需要O(n)空間苛让，可以排序氯窍，但是需要O(nlogn)時間。題目要求的是O(n)時間O(1)空間朴皆。哈希怎么利用現(xiàn)有空間來完成呢？
如果用異或操作的話，出現(xiàn)兩次的確實可以消掉斥扛，但是出現(xiàn)一次的兩個元素沒法求。
看了下tags也是提示的位操作丹锹，但是怎么用還是想不出來稀颁。
然后就看了答案，就是利用位操作然后得到兩個數(shù)的異或結(jié)果卷仑，再找出第一個不一樣的位峻村，將所有的數(shù)分為兩組分別進行異或操作麸折。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int n = nums.size();
vector<int> res{0, 0};
int diff = 0;
for (int i=0; i<n; i++)
diff ^= nums[i];
diff &= -diff; //重點在這里锡凝，找到第一個不同的位
for (int i=0; i<n; i++) {
if ((diff & nums[i]) == 0)
res[0] ^= nums[i];
else
res[1] ^= nums[i];
}
return res;
}
};
