Given an array of integers, every element appearsthreetimes except for one. Find that single one.

Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

如有疑問請聯系我：e-mail:yanghg@pku.edu.cn

看這題之前還是先看下Single Number，Single Number還是好理解的，但是到了升級版就變得很難理解了，這個也反映對了對位操作的薄弱，還是先復習下位操作，

1、“ & ” 按位與操作。應用場景：清除某些位，或者是取某些位的值，

2、“ | ” 按位與操作，應用場景：合并數據

3、“ ^ ”按位異或操作，應用場景：是特定位值取反，示例：a=tmp1,b=tmp2 交換兩個值且不引入第三變量，則可以這樣處理,a=tmp2^tmp1^tmp1 b=tmp1^tmp2^tmp2，看完3的介紹。Single Number就感覺它弱爆了。

回到這個題，對于這個題我其實也是一點想法都沒有！我感覺如果把這個題目解決了！那我們對于數列中有只會出現兩種類型數：1、出現n個2、只有一個數出現m個。也是能解決的。看我的分析

假如說現在有一個數組A={3，5，3，3}轉換成二進制A’={011,101,011,011}所有可以找到一些規律，同時出現三個數中每一位的1的個數一定是三個，單獨的那個一定是一個，那么就用三個變量來存儲每1的個數，也就是說，如果發現了一個位上的1到了三個那么就應該進行清零，循環比較一遍后剩下的那個統計1為一個的變量便是要得到的解。

循環遍歷數組每一個位置，“位操作的相加”，迭代操作。

設定變量：a,b,c=0,0,0;

a便是統計每一位1的個數，b便是統計出現兩個1，c便是統計出現三個，以下為每一次迭代的步驟；

1、b|=(a&A[i])；

2、a^=A[i];

3、c=~(a&b);

4、a&=c;

5、b&=c;

解釋：

1、先處理出現兩個1的問題，用a與A[i]進行與操作，用原來是1個1的情況判斷該位是否還有1，如果出現A[i]對應的位也是1，則說明該位是個兩個1，該位為0，則是一個1，不去處理，最后的結果與b進行或操作，將該位為兩個1的情況進行統計。（b的二進制表示：1，則表示該位有兩個1，0：則表示該位沒有兩個1）

2、用a統計出現該位一個1的數量，（1代表有一個1，0代表沒有1，如：a的第一位本身就是1，A[i]的第一位也是一，則不去統計，因為這是b要考慮的事情，兩個1的問題），a，A[i]對應位同時為1，則表示有兩個1，要進行進位，任何一個為1則要進行置1操作，其他情況為0，剛好符合 異或操作，

3、統計1出現三次的情況，如果該位已經是現在該位對應的a是1，b是1，則說明該位已經有3個1了，那么A[i]的該位也是1，則需要進行a、b的清零操作，分別用a b與c的取反進行與操作。

1、用b去統計

如果看不懂，我來以上述那個A數組為例子進行解釋

A’={011,101,011,011}，a=0,b=0c=0

1、A[0]=011、b=000,a=011,c=000

2、A[1]=101、b=001,a=110,c=000

3、A[2]=011、b=011,a=101 出現了ab有相同位為1的情況，c=110

4、A[2]=011,b=010,a=100,c=110

5、A[3]=011 b=010 a=111出現了ab有相同位為1的情況，c=101

6、A[4]=011 b=000 a=101 c=101

最后發現剩下的a剛好是A'中的單獨出現過的那個數字。

具體看代碼：

 1 public class Solution { 2     public int singleNumber(int[] A) { 3         int a=0,b=0,c=0; 4         for(int i=0;i<A.length;i++){ 5             b |= (a & A[i]); 6             a ^=A[i]; 7             c=~(a&b); 8             a&=c; 9             b&=c;10         }11         return a;12     }13 }