題目是這樣的：在一個(gè)整數(shù)數(shù)組中1個(gè)數(shù)出現(xiàn)了3次，其余的數(shù)都出現(xiàn)了2次，請(qǐng)找出出現(xiàn)3次的數(shù)。

建議大家自己先思考一下，我們下面直接給出了解法。

一、常規(guī)解法（3種）
1.用兩個(gè)循環(huán)，外層循環(huán)每次提供一個(gè)數(shù)，內(nèi)層循環(huán)遍歷數(shù)組進(jìn)行比對(duì)，用另外的變量存儲(chǔ)相等的次數(shù)，內(nèi)層循環(huán)結(jié)束之后，如果存儲(chǔ)次數(shù)的變量等于3，就輸出這個(gè)元素，然后退出，否則外層循環(huán)提供下一個(gè)值，繼續(xù)上述過(guò)程。

for（i=0；i＜SIZE；i++）
{
    n=0；
    for（j=0；j＜SIZE；j++）
        if（src[i]==src[j]）
            n++；
    if (n==3)
    {
        printf（"%d\n",src[i]);
        return；
    }
}

2. 建立一個(gè)臨時(shí)數(shù)組，初始化為0，遍歷一遍題目所給數(shù)組，將數(shù)組對(duì)應(yīng)的值記錄到新數(shù)組中，出現(xiàn)一次就++，所給數(shù)組的值和新數(shù)組的下標(biāo)一一對(duì)應(yīng)，然后遍歷新數(shù)組，讀出記錄的值。

for（i=0；i＜SIZE_src；i++）
    tmp[src[i]]++; //臨時(shí)數(shù)組tmp
for（i=0；i＜SIZE_tmp；i++)
    if (tmp[i]==3)
    {
        printf（"%d\n",i）;//打印下標(biāo)
        return；
     }

3. 先用快排排序，再遍歷數(shù)組，如果第i個(gè)數(shù)組元素與第i+1個(gè)相同就i+2,如果i與i+1，i+2都相同，就輸出，否則繼續(xù)下一輪循環(huán)。

for（i=0；i＜SIZE；i+=2） {
    if（src[i]==src[i+1]){
          if（src[i]==src[i+2]) {
              printf（"%d\n",i）; 
              return;}}}

二、最優(yōu)解
以上3種方法無(wú)疑都是可行的，但都不是最優(yōu)解，有的時(shí)間復(fù)雜度有問(wèn)題，有的無(wú)法估計(jì)邊界，有的代碼太復(fù)雜，也不是我們今天想講的。其實(shí)本題采用位運(yùn)算中異或是最簡(jiǎn)單的。

講之前要明確幾個(gè)知識(shí)點(diǎn)：（1）整數(shù)與0異或?yàn)楸旧?。與本身異或?yàn)?，即本身的奇數(shù)次異或還為本身，偶數(shù)次異或?yàn)?。（2）異或運(yùn)算符合結(jié)合律和交換律。有了以上兩點(diǎn)，本題很簡(jiǎn)單了，全部異或后，出現(xiàn)2次數(shù)的異或都為0，只剩出現(xiàn)3次的數(shù)了。

int singlenumber(int src[], int size)
{
    int result=0;
    for(int i=0; i<size; i++)
        result ^= src[i]; //遍歷數(shù)組全部異或
    return result;
}

三、變形推廣
看到這里，本題就可推廣為一個(gè)數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)全為偶數(shù)次，找出該數(shù)，以上代碼依舊沒有問(wèn)題。其實(shí)還可以有很多經(jīng)典變形，都是利用位運(yùn)算解決，但難度有所提高。請(qǐng)看如下兩個(gè)變形：

（1）若有兩個(gè)數(shù)出現(xiàn)了1次，其他數(shù)出現(xiàn)了2次，找出這兩個(gè)數(shù)。（原百度面試題）
（2）若有一個(gè)數(shù)出現(xiàn)了1次，其他數(shù)出現(xiàn)了3次，找出這個(gè)數(shù)。

我們先看第一題：現(xiàn)在數(shù)組中有兩個(gè)數(shù)字只出現(xiàn)1次，直接異或一次只能得到這兩個(gè)數(shù)字的異或結(jié)果，但光從這個(gè)結(jié)果肯定無(wú)法得到這個(gè)兩個(gè)數(shù)字。如果能將兩個(gè)數(shù)分開到二個(gè)數(shù)組中，那顯然符合上述“異或”解法的關(guān)鍵點(diǎn)了。因此這個(gè)題目的關(guān)鍵點(diǎn)就是將這兩個(gè)數(shù)分開到二個(gè)數(shù)組中。由于在二進(jìn)制上必定有一位是不同的。我們只需找出第一位不同的就行，這根據(jù)異或的結(jié)果就可以知道了，這個(gè)結(jié)果在二進(jìn)制上為1的位都說(shuō)明這兩個(gè)數(shù)在這一位上是不同的。

void fun(int src[], int size, int *n1, int *n2)
{
int i, j, result;
//計(jì)算這兩個(gè)數(shù)的異或結(jié)果
result = 0;
for (i = 0; i < size; i++)
result ^= src[i];

// 找第一個(gè)為1的位
for (j = 0; j < sizeof(int) * CHAR_BIT; j++)
if (((result >> j) & 1) == 1)
break;
// 這兩個(gè)數(shù)字在第j位上是不相同的,由此分組即可
*n1 = 0, *n2 = 0;
for (i = 0; i < n; i++){
     if (((src[i] >> j) & 1) == 0)
        *n1 ^= src[i];
else
    *n2 ^= src[i];
}}

再來(lái)看第二題：假如二進(jìn)制位不進(jìn)位的話，對(duì)數(shù)組中除了那個(gè)數(shù)以外的所有數(shù)做累加，每一位上的值都是3的倍數(shù)。而在加上這個(gè)數(shù)后，每一位取模3后，不是1就是0，組合起來(lái)就是該數(shù)了。（當(dāng)然還有更好的解法，能進(jìn)一步降低時(shí)間復(fù)雜度，用到了類似于邏輯電路的相關(guān)知識(shí)，難度又有所增加，在這里就不講了）

int singlenumber(int src[], int n) {
      int result = 0;
      int i, j,sum;
      for(i=0;i< sizeof(int) * CHAR_BIT;i++)
      {
          sum = 0;
          for(j=0;j<n;j++)
              sum += ((src[j]>>i)&1); //每輪一位做累加
           if(sum%3 == 1)
           result |= (1<<i);//確定每一位是否為1
        }
        return result;
    }

四、總結(jié)
各位，今天我們講的題目可以總稱為“尋找出現(xiàn)N次的數(shù)”，最本質(zhì)最核心的其實(shí)就是位運(yùn)算的靈活運(yùn)用，再怎么變換，到了最后都是巧用位運(yùn)算，這也是這類題最終想考察的知識(shí)點(diǎn)，希望今天的文章對(duì)大家有所啟發(fā)、有所幫助，就到這里吧，感謝耐心閱讀。

其實(shí)做為一個(gè)學(xué)習(xí)者，有一個(gè)學(xué)習(xí)的氛圍跟一個(gè)交流圈子特別重要這里我推薦一個(gè)C/C++基礎(chǔ)交流583650410，不管你是小白還是轉(zhuǎn)行人士歡迎入駐，大家一起交流成長(zhǎng)。