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?

如有疑問請聯(lián)系我：e-mail:yanghg@pku.edu.cn

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

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

2、“ | ” 按位與操作，應(yīng)用場景：合并數(shù)據(jù)

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

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

假如說現(xiàn)在有一個數(shù)組A={3，5，3，3}轉(zhuǎn)換成二進(jìn)制A’={011,101,011,011}所有可以找到一些規(guī)律，同時出現(xiàn)三個數(shù)中每一位的1的個數(shù)一定是三個，單獨的那個一定是一個，那么就用三個變量來存儲每1的個數(shù)，也就是說，如果發(fā)現(xiàn)了一個位上的1到了三個那么就應(yīng)該進(jìn)行清零，循環(huán)比較一遍后剩下的那個統(tǒng)計1為一個的變量便是要得到的解。

循環(huán)遍歷數(shù)組每一個位置，“位操作的相加”，迭代操作。

設(shè)定變量：a,b,c=0,0,0;

a便是統(tǒng)計每一位1的個數(shù)，b便是統(tǒng)計出現(xiàn)兩個1，c便是統(tǒng)計出現(xiàn)三個，以下為每一次迭代的步驟；

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

2、a^=A[i];

3、c=~(a&b);

4、a&=c;

5、b&=c;

解釋：

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

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

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

1、用b去統(tǒng)計

如果看不懂，我來以上述那個A數(shù)組為例子進(jìn)行解釋

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 出現(xiàn)了ab有相同位為1的情況，c=110

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

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

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

最后發(fā)現(xiàn)剩下的a剛好是A'中的單獨出現(xiàn)過的那個數(shù)字。

具體看代碼：

 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 }