這個(gè)題來自《劍指offer》但是書上上感覺講解不太詳細(xì)，還是看博客吧（我把下面博客改寫成了C++版本運(yùn)行通過）

注意這個(gè)題的相關(guān)代碼中，輸入的數(shù)組只能有兩個(gè)數(shù)出現(xiàn)一次，如果有第三個(gè)數(shù)出現(xiàn)一次，那么這個(gè)代碼就會失效。

總結(jié)下算法思路：

假設(shè)原始數(shù)組中只出現(xiàn)一次的元素是A和B，原始數(shù)組為{A,E,C,D,C,D,E,B}

主要是利用異或的交換律。

先把所有數(shù)字按次序進(jìn)行異或運(yùn)算，得到的結(jié)果必然是A⊕B，因?yàn)槠渌囟际浅霈F(xiàn)兩次的，根據(jù)異或運(yùn)算的交換律有

A⊕E⊕C⊕D⊕C⊕D⊕E⊕B=A⊕B⊕C⊕C⊕D⊕D⊕E⊕E=A⊕B

這個(gè)A⊕B中可能有多個(gè)比特位是1，我們?nèi)∽钣覀?cè)的一個(gè)bit(其實(shí)其他bit也行)

先把原始數(shù)組拆成兩份，怎么拆呢？利用上面的那個(gè)A⊕B的最右側(cè)的值為1的bit位（其他位置為0），

和這個(gè)bit位&結(jié)果為非0的歸為1組并進(jìn)行異或運(yùn)算（異或運(yùn)算的初始值為0），

和這個(gè)bit位&結(jié)果為0的歸為另外1組并進(jìn)行異或運(yùn)算（異或運(yùn)算的初始值為0）

在歸為一組的同時(shí)進(jìn)行異或運(yùn)算，所以其實(shí)這里再次使用了異或運(yùn)算的交換律，

因?yàn)镃，D，E都出現(xiàn)兩次，無論歸為哪一組，異或結(jié)果都是0，我們可以不關(guān)心。

好了，所以其實(shí)就是剩下的A和B與上面的bit進(jìn)行運(yùn)算的結(jié)果是最關(guān)鍵的。

因?yàn)锳⊕B的最右側(cè)的bit位表示了A和B在二進(jìn)制的某位上的不一致，也就是在這個(gè)位上必定一個(gè)是1，一個(gè)是0，

所以當(dāng)A和（A⊕B的最右側(cè)的bit位）進(jìn)行&運(yùn)算時(shí)，要么相等，要么不相等。

相等時(shí)丟入其中一組去做異或運(yùn)算，因?yàn)槠渌囟际浅霈F(xiàn)兩次，所以最終異或結(jié)果肯定是這個(gè)只出現(xiàn)一次的數(shù)

不相等時(shí)丟入其中一組去做異或運(yùn)算，因?yàn)槠渌囟际浅霈F(xiàn)兩次，所以最終異或結(jié)果肯定是這個(gè)只出現(xiàn)一次的數(shù)

文章轉(zhuǎn)載自：

https://segmentfault.com/a/1190000004886431

260.Single Number II 原題鏈接

• 本題其實(shí)算是比較簡單，在 leetcode 上也只是 medium 級別，ac 率也很高，最好先自己嘗試，本文只是單純的記錄一下自己整體的思路；

• 在閱讀本文章之前，最好先解鎖本題的簡單模式 136.Single Number，這對理解本題有較大的幫助；

• 還有很多細(xì)節(jié)作者都沒有寫進(jìn)去，是為了留給讀者一點(diǎn)思考的空間，其實(shí)是因?yàn)閼?#xff1b;

• 由于作者個(gè)人水平等原因，出現(xiàn)錯(cuò)誤在所難免，還望各位看官海涵。

注意 Note 中的第一個(gè)條件：The order of the result is not important.，這個(gè)條件非常重要，這關(guān)系到算法的正確性。

---

然后給出整個(gè)算法的具體思路，假設(shè)數(shù)組中兩個(gè)不同的數(shù)字為 A 和 B；

通過遍歷整個(gè)數(shù)組并求整個(gè)數(shù)組所有數(shù)字之間的 XOR，根據(jù) XOR 的特性可以得到最終的結(jié)果為 AXORB = A XOR B；

通過某種特定的方式，我們可以通過 AXORB 得到在數(shù)字 A 和數(shù)字 B 的二進(jìn)制下某一位不相同的位；因?yàn)锳 和 B 是不相同的，所以他們的二進(jìn)制數(shù)字有且至少有一位是不相同的。我們將這一位設(shè)置為 1，并將所有的其他位設(shè)置為 0，我們假設(shè)我們得到的這個(gè)數(shù)字為 bitFlag；

那么現(xiàn)在，我們很容易知道，數(shù)字 A 和 數(shù)字 B 中必然有一個(gè)數(shù)字與上 bitFlag 為 0；

?因?yàn)閎itFlag 標(biāo)志了數(shù)字 A 和數(shù)字 B 中的某一位不同，那么在數(shù)字 A 和 B 中的這一位必然是一個(gè)為 0，另一個(gè)為 1；

而我們在 bitFlag 中將其他位都設(shè)置為 0，那么該位為 0 的且只出現(xiàn)一次的數(shù)字& bitFlag 就等于 0，而該位為 1 的且只出現(xiàn)一次的數(shù)字與上 bitFlag 就等于 bitFlag

現(xiàn)在問題就簡單了，我們只需要在循環(huán)一次數(shù)組，將與上 bitFlag 為 0 的數(shù)字進(jìn)行 XOR 運(yùn)算，與上 bitFlag 不為 0 的數(shù)組進(jìn)行獨(dú)立的 XOR 運(yùn)算。那么最后我們得到的這兩個(gè)數(shù)字就是 A 和 B。

先給出具體實(shí)現(xiàn)，引用自 proron's Java bit manipulation solution，我修改了部分代碼以便于理解：

#include<iostream> ? using namespace std; int* singleNumber(int* nums,int length) {int AXORB = 0;for (int i = 0; i<length; i++){AXORB ^= nums[i];}//這里利用的是異或運(yùn)算的交換律，最終結(jié)果等于兩個(gè)只出現(xiàn)一次的元素的抑或//即：AXORB=A 異或 B// pick one bit as flagcout << "AXORB=" << AXORB << endl;cout << "AXORB-1=" << AXORB - 1 << endl;int bitFlag = (AXORB & (~(AXORB - 1)));cout << "bigFlag=" << bitFlag << endl;//使用這個(gè)bitFlag來給原始數(shù)組進(jìn)行分類，分成2類，//之所以分成兩類是希望每一個(gè)類都有一個(gè)只出現(xiàn)一次的數(shù)即A或者Bint *res = new int[2];res[0] = res[1] = 0;//這里不要忘記初始化。for (int i = 0; i<length; i++){cout << "i=" << i << endl;cout << "nums[i]=" << nums[i] << endl;if ((nums[i] & bitFlag) == 0){cout << "res[0]=" << res[0] << endl;res[0] ^= nums[i];//這里再次利用異或運(yùn)算的交換律。//因?yàn)榉殖闪藘深?#xff0c;所以其中一類不停地運(yùn)算，最終結(jié)果一定是只出現(xiàn)一次的數(shù)。}//例如6^3^5^5^3=6^3^3^5^5=6//下面的else中同理else {cout << "res[1]=" << res[1] << endl;res[1] ^= nums[i];}cout << "-------------------------" << endl;}return res; }int main() {int nums[8] = { 2,4,3,6,3,2,5,5 };int *result = singleNumber(nums,sizeof(nums)/sizeof(nums[0]));cout << "--------main----------" << endl;cout << result[0] << endl;cout << result[1] << endl;cin.get();cin.get();return 0; }

接下來，我們一行行的解析代碼：

int AXORB = 0; for(int num: nums){AXORB ^= num; }

這段代碼在 136.Single Number 已經(jīng)解析過，很容易理解最后得到的結(jié)果：假設(shè)數(shù)組中不同的數(shù)字為 A 和 B，那么 最后得到的結(jié)果是 A XOR B。

隨后的這一行代碼是整個(gè)算法中的難點(diǎn)：

//pick one bit as flag int bitFlag = (AXORB & (~ (AXORB - 1)));

這一行代碼的作用是：找到數(shù)字 A 和數(shù)字 B 中不相同的一位，并將該位設(shè)置為 1，其他位設(shè)置為 0；
根據(jù) XOR 的定義，我們知道，在 AXORB 中，為 1 的位即 A 和 B 不相同的位，AXORB 中為 0 的位即 A 和 B 中相同的位
所以，要找到 A 和 B 中不相同的位，只需要找到在 AXORB 中從右往左第一個(gè)為 1 的位，保留該位并將其他位置為 0 即可。

//其實(shí)這一行與下面的代碼等價(jià)，但是論逼格就差遠(yuǎn)了（手動斜眼 public static int f(int num){int times = 0;while(num > 0){if(num % 2 == 1){break;}times++;num = num >> 1;}return 1 << times; } //下面這個(gè)返回 true System.out.println(Stream.iterate(1, num -> num + 1).limit(Integer.MAX_VALUE).allMatch(num -> f(num)==(num & (~(num -1)))));

我們可以把這一行代碼解析為三步：

int tmp0 = AXORB - 1;

• 假設(shè) AXORB 從右往左出現(xiàn)的第一位非 0 數(shù)字出現(xiàn)在第k位，那么數(shù)字 AXORB 可以表示為，可能等于 0：

如果 a0 = 1；那么問題非常簡單， AXORB - 1 可以表示為：

int tmp1 = ~tmp0;

int bitFlag = AXORB & tmp1;

由前面假設(shè)我們知道 a0=1，所以很明顯， bitFlag = 1;

如果 a0 != 1，我們同樣很容易得出這一行代碼的作用就是將數(shù)字 AXORB 的從右到左第一個(gè)出現(xiàn) 1 的位置為 1，其他位全部置為 0。其實(shí)一點(diǎn)都不容易，只不過用 laTex 寫數(shù)學(xué)公式好蛋疼啊，所以偷下懶

到這里，整個(gè)算法基本上就沒什么難點(diǎn)了，大家自行理解吧。

我了個(gè)大槽，我本來只是想試試新學(xué)的 laTex，結(jié)果他喵的就寫了這么多。大寫加粗的坑

總結(jié)

以上是生活随笔為你收集整理的leetcode 算法解析（一）：260. Single Number III（C++版本和自己的注解）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。