如何快速找出數(shù)組中出現(xiàn)一半以上的數(shù)字

題目：

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。

1 哈希表

用哈希表記錄每個元素出現(xiàn)的次數(shù)，如果該元素出現(xiàn)次數(shù)超過一半，返回該元素。
時間復(fù)雜度O（n）
空間復(fù)雜度O（n）

很容易看出來，該算法使用了HashMap作為額外的空間，因此該算法的空間復(fù)雜度為O(n)，我們接下來看一種空間復(fù)雜度為O(1)的算法。

2 幸存者(候選者)算法

我給這個算法起了一個比較有趣的名字，叫做幸存者(候選者)算法?；镜乃悸肥?，在遍歷數(shù)組過程中，每次找到一對不相等的數(shù)，給砍掉，最后活下來的幸存者就是有可能是整個數(shù)組中出現(xiàn)的次數(shù)超過數(shù)組長度的一半的那個數(shù)。

例如{1,2,3,2,2,2,5,4,2}

1） 1≠2，砍掉這兩個數(shù)

2）3≠2，砍掉這兩個數(shù)

3）2≠5，砍掉這兩個數(shù)

4）4≠2，砍掉這兩個數(shù)

至此，沒得砍了，2成為了最后的幸存者，那這個2就有可能是整個數(shù)組中出現(xiàn)的次數(shù)超過數(shù)組長度的一半的那個數(shù)，所以我們還要遍歷一遍數(shù)組，看看2是否是真的出現(xiàn)一半。

那如何實(shí)現(xiàn)呢？該算法我覺得實(shí)在是太妙了！而且只需要遍歷一遍數(shù)組就能夠知道那個幸存者是哪個數(shù)字。

我們準(zhǔn)備兩個變量，cand和times，cand為候選數(shù)字，而times表示候選數(shù)字出現(xiàn)的次數(shù)。

1）遍歷1，把cand置為1，而times也變?yōu)?(因?yàn)?這個候選人出現(xiàn)了一次)

2）遍歷2，發(fā)現(xiàn)2和cand不相等，那么我們要開砍了，怎么砍呢？只需要把times減1即可，times變?yōu)?了。在我們的潛意識里，1和2這一對不相等的數(shù)已經(jīng)被砍掉了，妙吧~

3）上一步已經(jīng)把times置為0了，說明沒有候選人了，當(dāng)我們遍歷3的時候，重新把3立為候選人。

4）2≠cand(3)，砍掉，times減一。

5）2重新立為候選人

6）2這個候選人出現(xiàn)次數(shù)++，times變?yōu)?

7）5≠2，砍掉，只需要將times減一即可，times變?yōu)?了，含義就是5和2都被砍掉了。

8）4≠2，砍掉，將times減一，times變?yōu)?了，候選人又沒了，4和2都被砍掉了。

9）2重新立為候選人

10）最后候選人為2，2就有可能是整個數(shù)組中出現(xiàn)的次數(shù)超過數(shù)組長度的一半的那個數(shù)

11）重新遍歷一遍數(shù)組，看看2是不是真的是整個數(shù)組中出現(xiàn)的次數(shù)超過數(shù)組長度的一半的那個數(shù)

很明顯，只需要兩個變量就能完成這個任務(wù)，不需要O(n)的空間復(fù)雜度啦。

完1