只出現一次的數字i

題目描述

題目分析

xxxx這道題第一次看的時候是完全沒有思路的，想出來的方法效率太低，后來在網上看到解法是使用異或，但是一直不理解原理是什么，最近學校在學“計算機組成原理”，詳細學異或后，突然對這個題有了透徹的理解，題目分析如下：

首先來了解一下異或這個運算子
異或（^）:相同為0，相異為1

于是這種機理就可以很好的運用到解決這個問題當中，因為相同的數，在32個位元位的數分別相同，所以當相同的數字進行異或時，得到的結果將是32個比
特位全為0，得到的就是數字0，同時0與任何數字異或得到的仍然是該數字，
詳細如圖：

xxxx值得注意的是，最終異或的結果與數字的順序無關，因為所有數字某一個位元位0、1數字個數一樣的，異或起來值是一定的，與順序無關，

代碼實作：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
    	//最終的結果保存到變數a中
        int a = 0;
        for(size_t i = 0; i<nums.size(); i++)
        	//a與每一個數字異或
            a ^= nums[i];
        //a就是單獨的那個數字
        return a;
    }
};

只出現一次的數字ii

題目描述

題目分析

xxxx不同上一個題，這個題目是只有一個數字出現一次，其余數字出現三次，顯然無法使用上個題目的解法，但是大的思路還是對位元位進行操作，突破口就是想一下，這些數字的位元位有什么區別于聯系，容易想到的是，對于每個數字的第i個位元位（1≤i≤32）來說，要么有些數字是1，要么是0，那么將每個數字同一位元位的1統計出來第，統計的結果要么是3的倍數，要么是3的倍數+1，而且，那些3的倍數+1的位元位，一定是只出現過一次的那個數字為1的位元位，
舉一個例子：

xxxx在統計完所有數字每一位為1的個數后，我們就可以篩選出哪些位元位1的數字為3的倍數+1，這些位就是只出現一次數字的為1的位元位，然后我們就可以得到
這個唯一的數值了，

代碼實作

class Solution {
public:
    int singleNumber(vector<int>& nums) {
    	//cout陣列用來存放統計32個位元位分別有多少個1
        int count[32] = {0};
        for(int i=0;i<nums.size();i++)
        {
            for(int j=0;j<32;j++)
            {
            	//nums[i]&1得到該為是1還是0
                count[j] += (nums[i]&1);
                //>>用于一次獲取一個數字的每一位
                nums[i] = nums[i]>>1;
            }
        }
        int number = 0;
        for(int i=0;i<32;i++)
        {
        	//如果是3的倍數+1
            if(count[i]%3 == 1)
            {
            	// number |= (1<<i)比較難理解，在下面展開具體說明
                number |= (1<<i);
            }
        }
        return number;
    }
};

"number |= (1<<i)" 的詳細解讀：i從0~31,因此1<< i就是以此產生不同的二進制中只有一個1其余全為0的數字，這樣就可以與結果數字的位元位中應該1的位置依次或運算，最終得到結果，
如圖：

只出現一次的數字iii

題目描述

題目分析

xxxx看到這個題是不是感覺很熟悉，很親切，似乎好像感覺跟上面的第一題十分相似，但是為啥一個是簡單分類，一個是中等難度分類，頓時心中一涼，就像上學時候，這題看的這么眼熟，就是不會做，我也是在這道題卡了很久，感覺需要用到第一題的思路，但是這里有兩個只出現一次的數字，生搬硬套肯定是不行的，想要轉移的第一道題，關鍵就是把這兩個只出現一次的數字分開，然后我們就可以對分開的兩組數字，分別套用第一題的思路，就找出來了兩個只出現一次的數字所以，關鍵就在于，如何將這一組資料分成兩組，并且保證這兩個出現一次的數字還分別在兩個組，
xxxx毫無疑問，我們還是需要利用他們的二進制來找突破口，想要將他們分成兩組，那么就需要找出他們的不同之處，那就是，對于不同的數字，他們的32個位元位不可能完全相同，所以必然有某幾位不相同，我們就可以依據這個條件來把一組資料分成兩組，該位元位為1的一組，為0的另一組，同時，其他成對出現的數字中，有可能該位元位為1或者為0.，不管他們具體如何，在分成兩組之后，每一組都會退化成第一題的情況，那就是只有一個出現一次的數字，其余數字都是成對出現，再使用第一題的思路即可解決，
xxxx但是如何找出那個關鍵的位元位呢？我們可以將所有數字異或，通過之前的知識，我們知道，所有數字異或，成對出現的數字全部抵消，剩下的就是兩個只出現過一次的數字，然后他們異或產生的數字，必然不可能是0，所以就會有其中一個位元位值為1，該位元位就是兩個數字不同的位元位之一，

代碼實作

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
    	//val用于存盤所有數字異或的結果
        int val;
        for(int j=0;j<nums.size();j++)
            val ^= nums[j];
        //i用來存盤第幾個位元位是1
        int i = 0;
        //找到val第幾個位元位的值為1
        //不是1，就進入回圈，i++
        while(!(1&(val>>i)))
        {
            i++;
        }
        //創建兩個vector，存放分成的兩組資料
        vector<int> v1;
        vector<int> v2;
        //分組
        for(int j=0;j<nums.size();j++)
        {
        	//第i+1為是1的放入v1
            if(nums[j]&(1<<i))
                v1.push_back(nums[j]);
            //第i+1為是0的放入v2
            else
                v2.push_back(nums[j]);
        }
        //套用第一題的思路
        int a = 0,b = 0;
        for(int j=0;j<v1.size();j++)
            a ^= v1[j];
        for(int j=0;j<v2.size();j++)
            b ^= v2[j];
        vector<int> ret;
        ret.push_back(a);
        ret.push_back(b);
        return ret;
    }
};

總結

這三道題的答題思路是相同的，都是使用了位運算，因為數字完全未知，我們要找數字之間的相同點與不同點，就需要依賴他們的二進制數，不同數字的二進制數一定不一樣，相同數字的二進制數一定一樣，
同時我們還需要掌握的就是，相同數字異或為0,0與任何數字異或為它本身，這個小技巧還用于不適用臨時變數交換兩個數字，
好啦，本文內容到此結束，如果思路和代碼還有什么優化和改進的地方請在評論區發表，或者直接私信我，讓我們共同學習共同進步！