題目

給定一個數組，在這個數組中，包含了一些整形數字，除了有兩個數字重復了一次，其他數字都重復了兩次。找出這兩個數字。空間復雜度盡可能做到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;
    }
};