题目
给定一个数组，在这个数组中，包含了一些整形数字，除了有两个数字重复了一次，其他数字都重复了两次。找出这两个数字。空间复杂度尽可能做到O(1)。
分析
尽管解决方案中要求空间复杂度为O(1)，这个方法确实有点复杂和难想，而且很难写出常数小的算法。
感受异或的神奇
上面这个链接中给出了这道题的标准做法。在这个方法中，首先将所有字母进行异或操作，然后，结果就是两个只出现了一次的数字的异或。这个数字的每一位1意味着这两个数字的哪几位是不同的。任取一位，在这一位上，将数组分为两类，一类是这一位上是1，另一类是这一位上是0，这样对这两个数组分别异或结果就是这两个数字了。
这利用了异或的性质。
a ^ b ^ c = a ^ c ^ b
a ^ a = 0
0 ^ a = a
a ^ b = c => a ^ c = b
运行13ms，击败68%提交。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int axorb = 0, last = 0;
vector<int> ret(2, 0);
for(auto it = nums.begin(); it!=nums.end() ; it++)
{
axorb ^= *it;
}
last = axorb & (~(axorb - 1));
for(auto it = nums.begin(); it!=nums.end() ; it++)
{
if ((last & *it) != 0)
ret[0] ^= *it;
}
ret[1] = axorb ^ ret[0];
return ret;
}
};
其他方法
如果不要求空间复杂度为常数，其实也可以用哈希表来做。这样算法的扩展性很好，而且也不晦涩。
运行16ms，击败%34提交
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unordered_set<int> buff(nums.size());
for(auto i = nums.begin(); i!=nums.end() ; i++)
{
auto it = buff.find(*i);
if(it == buff.end()){
buff.insert(*i);
}
else{
buff.erase(it);
}
}
vector<int> ret;
for(const int & i : buff){
ret.push_back(i);
}
return ret;
}
};
