作者：翟天保Steven
版權(quán)聲明：著作權(quán)歸作者所有，商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處

題目描述：

一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字只出現(xiàn)一次，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。

數(shù)據(jù)范圍：數(shù)組長(zhǎng)度2≤n≤1000，數(shù)組中每個(gè)數(shù)的大小0<val≤1000000
要求：空間復(fù)雜度O(1)，時(shí)間復(fù)雜度O(n)

提示：輸出時(shí)按非降序排列。

示例：

輸入：

[1,4,1,6]

返回值：

[4,6]

說(shuō)明：

返回的結(jié)果中較小的數(shù)排在前面   

解題思路：

本題考察位運(yùn)算。兩種解題思路。

1）暴力法

? ? ? ?使用哈希表記錄出現(xiàn)頻率，將頻率為1的數(shù)輸出即可。該方法的空間復(fù)雜度不符合題目要求。

2）異或運(yùn)算

? ? ? ?異或運(yùn)算指兩個(gè)數(shù)相同為0，不相同為1。因?yàn)槌艘獙ふ业臄?shù)字出現(xiàn)了一次，其他數(shù)字都出現(xiàn)了兩次，所以將這些數(shù)字進(jìn)行異或運(yùn)算后，根據(jù)其特性，重復(fù)出現(xiàn)的數(shù)字抵消了，只保留了出現(xiàn)了一次的數(shù)字。

? ? ? ?如4^1^2^1^2。4為100,1為001,2為010,4^1得到101,再^2得到111，再^1得到110，再^2得到100，即4。

? ? ? ?那如果有兩個(gè)出現(xiàn)了一次的數(shù)字，則結(jié)果就相當(dāng)于這兩個(gè)數(shù)字異或。如4^1^2^1^2^3，最終的結(jié)果就是111，即4^3。

? ? ? ?本題目要求輸出這兩個(gè)數(shù)字，那如何將111拆開(kāi)呢？4和3，如果某一位不相同，則異或結(jié)果該位就是1，我們定義t從001開(kāi)始，將t與111與運(yùn)算，尋找哪一位首次出現(xiàn)了1；111中最右即為1，說(shuō)明在00x的位置，數(shù)字4和3是不一樣的；再次遍歷，將所有數(shù)據(jù)根據(jù)該位的數(shù)字分類，這樣就能得到兩個(gè)組，數(shù)字為1的組結(jié)果就是3，數(shù)字為0的組結(jié)果就是4。

? ? ? ?不得不說(shuō)，這題目就是為這個(gè)解法量身定做的。。。各個(gè)條件完美匹配emm

測(cè)試代碼：

1）暴力法

class Solution {
public:
    // 尋找出現(xiàn)一次的數(shù)字
    vector<int> FindNumsAppearOnce(vector<int>& nums) {
        unordered_map<int,int> um;
        vector<int> result;
        // 遍歷數(shù)組
        int size = int(nums.size());
        for(int i = 0; i < size; ++i){
            um[nums[i]]++;
        }
        // 尋找出現(xiàn)頻率為1的數(shù)
        for(int i = 0; i < size; ++i){{
            if(um[nums[i]] == 1){
                result.emplace_back(nums[i]);
            }
        }}
        // 按大小順序輸出
        if(result[0] < result[1]){
            return result;
        }
        else{
            return { result[1], result[0] };
        }
    }
};

2）異或運(yùn)算

class Solution {
public:
    // 尋找出現(xiàn)一次的數(shù)字
    vector<int> FindNumsAppearOnce(vector<int>& nums) {
        vector<int> result{ 0, 0};
        // 遍歷數(shù)組進(jìn)行異或運(yùn)算
        int temp = 0;
        int size = int(nums.size());
        for(int i = 0; i < size; ++i){
            temp ^= nums[i];
        }
        // 找到兩個(gè)數(shù)不相同的第一位
        int t = 1;
        while((t & temp) == 0){
            t <<= 1;
        }
        // 再次遍歷，將t位為1的數(shù)歸為1組，為0的數(shù)歸為1組，這樣兩組的異或運(yùn)算得到的結(jié)果就是兩個(gè)不重復(fù)數(shù)
        for(int i = 0; i < size; ++i){
            if((t & nums[i]) == 0){
                result[0] ^= nums[i];
            }
            else{
                result[1] ^= nums[i];
            }
        }
        // 按大小順序輸出
        if(result[0] < result[1]){
            return result;
        }
        else{
            return { result[1], result[0] };
        }
    }
};