題目描述 [數(shù)組中只出現(xiàn)一次的數(shù)字]

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

解題思路一

hashmap

代碼

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        unordered_map<int, int> hashmap;
        for(auto num:data)
            hashmap[num]++;

        vector<int> res;
        for(auto it:hashmap){
            if(it.second==1)
                res.push_back(it.first);
        }
        *num1 = res[0];
        *num2 = res[1];
    }
};

解題思路二

轉(zhuǎn)自 https://blog.csdn.net/zh_ang_lei/article/details/50908074

1. 首先交待一下異或的基本性質(zhì)：2個(gè)相同的數(shù)異或等于0，且異或操作(^)滿足結(jié)合律和交換律。

2. 再來考慮一種簡(jiǎn)單一點(diǎn)的情況：一個(gè)數(shù)組中只有一個(gè)元素出現(xiàn)唯一的一次，而有其他元素都出現(xiàn)2次。那么我們用0依次異或數(shù)組中每一個(gè)元素，得到的就是那個(gè)唯一的元素。因?yàn)槲覀兛梢岳媒粨Q律和結(jié)合律將相同的元素移動(dòng)到一起，那么在利用結(jié)合律，相同的元素兩兩先異或，得到0，最后得到很多0和唯一的元素異或，所以最終的答案就是那個(gè)唯一的元素。

3. 所以，如果我們能把原來問題中的數(shù)組，分成2個(gè)子數(shù)組，使得每個(gè)子數(shù)組中都只有一個(gè)唯一的元素以及很多成對(duì)的元素，那么我們就可以求出每個(gè)子數(shù)組中唯一的元素，最終就可以得到原數(shù)組中2個(gè)出現(xiàn)次數(shù)唯一的元素。

方法是這樣的：

• 首先數(shù)組中所有元素依次異或，因?yàn)橄嗤脑禺惢虻玫?，所以最終的答案就等于那2個(gè)唯一的元素a^b的值。

• 因?yàn)閍,b不同，所以異或得到的答案肯定是不等于0的，那么我們就找到a^b的二進(jìn)制表示中第一個(gè)為1的位，假如是第k位。而a,b兩個(gè)數(shù)在第k位上是不同的，一個(gè)為0，一個(gè)為1

• 接下來我們將第k位是1的分成一組，第k位是0的分成一組，如果2個(gè)元素相同，那么他們第k位肯定是一樣的，所以肯定被分到同一組中。而a,b則被分到2組中去了。

• 然后我們就可以在每個(gè)分組中異或每一個(gè)元素，最終就可以得到那2個(gè)唯一的元素。

代碼

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int num = data.size();

        int ret = 0;
        for(int i=0; i<num; i++)
            ret ^= data[i];

        //找到第一個(gè)k位
        int pos = 1;
        while(((ret>>pos) & 1) != 1 )
            pos++;

        //將包含num1 and num2 分開
        for(int i=0; i<num; i++)
        {
            if(((data[i]>>pos) & 1) != 1 )
                *num1 ^= data[i];
            else
                *num2 ^= data[i];
        }
    }
};