题解 | #数组中只出现一次的两个数字#

开始时没看到空间复杂度的要求，选择使用键值对来存储数组信息。
第一次遍历数组，将数组中的数字及其出现次数记录到map中。
第二次遍历map，找到其中仅出现过1次的数，加入到结果数组中返回。

这种做法提交后运行时间打败前100%还让我有点小激动。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        map<int, int> valueMap;
        vector<int> result;
        for(int i = 0;i < array.size();i++){
            if(valueMap.find(array.at(i)) == valueMap.end()){
                valueMap.insert(pair<int,int>(array.at(i),1));
            }
            else{
                valueMap[array.at(i)]++;
            }
        }
        map<int, int>::iterator iter = valueMap.begin();
        while(iter != valueMap.end()){
            if(iter->second == 1){
                result.push_back(iter->first);
                if(result.size() > 1){
                    return result;
                }
            }
            iter++;
        }
        return result;
    }
};

上面的做法中使用了一个map，所以空间复杂度为O(n)，未满足题目要求。下面考虑空间复杂度为O(1)的做法。
首先需要知道的是，两个相同的数异或为0，即a^a=0，而异或运算满***换律，即a^b^a=a^a^b。
可以看出，在一条很长的连续异或运算中，偶数次重复的数对结果没有影响，最终产生影响的是奇数次重复数。在本体中，将所有数异或后，得到的是仅出现一次的那两个数的异或。
而异或的结果中为1的位数就是这两个数不同的位数，所以可以通过异或结果中其中的一个1来区分这两个数。最终将整个数组分成两部分异或，得到两个数即为结果。
这样做时间复杂度O(n)，空间复杂度O(1)，满足题目要求。但是值得注意的是跟上面的做法比起来运行时间还是慢了不少。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        int num = 0;
        for(int i = 0;i < array.size();i++){
            num ^= array.at(i);
        }
        int com = 1;
        while((num & com) == 0){
            com <<= 1;
        }
        int num1 = 0;
        int num2 = 0;
        for(int i = 0;i < array.size();i++){
            if(array.at(i) & com){
                num1 ^= array.at(i);
            }
            else{
                num2 ^= array.at(i);
            }
        }
        return num1 > num2 ? vector<int>{num2, num1} : vector<int>{num1, num2};
    }
};