## 題目描述 題目：數組中有一個數字出現的次數超過了數組長度的一半，找出這個數字。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.03.md#分析與解法)分析與解法 一個數組中有很多數，現在我們要找出其中那個出現次數超過總數一半的數字，怎么找呢？大凡當我們碰到某一個雜亂無序的東西時，我們人的內心本質期望是希望把它梳理成有序的。所以，我們得分兩種情況來討論，無序和有序。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.03.md#解法一)解法一 如果**無序**，那么我們是不是可以先把數組中所有這些數字**先進行排序**（至于排序方法可選取最常用的快速排序）。排完序后，直接遍歷，在遍歷整個數組的同時統計每個數字的出現次數，然后把那個出現次數超過一半的數字直接輸出，題目便解答完成了。總的時間復雜度為O(nlogn + n)。 但**如果是有序的數組呢**，或者經過排序把無序的數組變成有序后的數組呢？是否在排完序O(nlogn)后，還需要再遍歷一次整個數組？ 我們知道，既然是數組的話，那么我們可以根據數組索引支持直接定向到某一個數。我們發現，一個數字在數組中的出現次數超過了一半，那么在已排好序的數組索引的N/2處（從零開始編號），就一定是這個數字。自此，我們只需要對整個數組排完序之后，然后直接輸出數組中的第N/2處的數字即可，這個數字即是整個數組中出現次數超過一半的數字，總的時間復雜度由于少了最后一次整個數組的遍歷，縮小到O(n*logn)。 然時間復雜度并無本質性的改變，我們需要找到一種更為有效的思路或方法。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.03.md#解法二)解法二 既要縮小總的時間復雜度，那么可以用查找時間復雜度為O(1)的**hash表**，即以空間換時間。哈希表的鍵值（Key）為數組中的數字，值（Value）為該數字對應的次數。然后直接遍歷整個**hash表**，找出每一個數字在對應的位置處出現的次數，輸出那個出現次數超過一半的數字即可。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.03.md#解法三)解法三 Hash表需要O(n)的空間開銷，且要設計hash函數，還有沒有更好的辦法呢？我們可以試著這么考慮，如果**每次刪除兩個不同的數**（不管是不是我們要查找的那個出現次數超過一半的數字），那么，在剩下的數中，我們要查找的數（出現次數超過一半）出現的次數仍然超過總數的一半。通過不斷重復這個過程，不斷排除掉其它的數，最終找到那個出現次數超過一半的數字。這個方法，免去了排序，也避免了空間O(n)的開銷，總得說來，時間復雜度只有O(n)，空間復雜度為O(1)，貌似不失為最佳方法。 舉個簡單的例子，如數組a[5] = {0, 1, 2, 1, 1}; 很顯然，若我們要找出數組a中出現次數超過一半的數字，這個數字便是1，若根據上述思路4所述的方法來查找，我們應該怎么做呢？通過一次性遍歷整個數組，然后每次刪除不相同的兩個數字，過程如下簡單表示： ~~~ 0 1 2 1 1 =>2 1 1=>1 ~~~ 最終1即為所找。 但是數組如果是{5, 5, 5, 5, 1}，還能運用上述思路么？很明顯不能，咱們得另尋良策。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.03.md#解法四)解法四 更進一步，考慮到這個問題本身的特殊性，我們可以在遍歷數組的時候保存兩個值：一個candidate，用來保存數組中遍歷到的某個數字；一個nTimes，表示當前數字的出現次數，其中，nTimes初始化為1。當我們遍歷到數組中下一個數字的時候： * 如果下一個數字與之前candidate保存的數字相同，則nTimes加1； * 如果下一個數字與之前candidate保存的數字不同，則nTimes減1； * 每當出現次數nTimes變為0后，用candidate保存下一個數字，并把nTimes重新設為1。 直到遍歷完數組中的所有數字為止。 舉個例子，假定數組為{0, 1, 2, 1, 1}，按照上述思路執行的步驟如下： * 1.開始時，candidate保存數字0，nTimes初始化為1； * 2.然后遍歷到數字1，與數字0不同，則nTimes減1變為0； * 3.因為nTimes變為了0，故candidate保存下一個遍歷到的數字2，且nTimes被重新設為1； * 4.繼續遍歷到第4個數字1，與之前candidate保存的數字2不同，故nTimes減1變為0； * 5.因nTimes再次被變為了0，故我們讓candidate保存下一個遍歷到的數字1，且nTimes被重新設為1。最后返回的就是最后一次把nTimes設為1的數字1。 思路清楚了，完整的代碼如下： ~~~ //a代表數組，length代表數組長度 int FindOneNumber(int* a, int length) { int candidate = a[0]; int nTimes = 1; for (int i = 1; i < length; i++) { if (nTimes == 0) { candidate = a[i]; nTimes = 1; } else { if (candidate == a[i]) nTimes++; else nTimes--; } } return candidate; } ~~~ 即針對數組{0, 1, 2, 1, 1}，套用上述程序可得： ~~~ i=0，candidate=0，nTimes=1； i=1，a[1] != candidate，nTimes--，=0； i=2，candidate=2，nTimes=1； i=3，a[3] != candidate，nTimes--，=0； i=4，candidate=1，nTimes=1； 如果是0，1，2，1，1，1的話，那么i=5，a[5] == candidate，nTimes++，=2；...... ~~~ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.03.md#舉一反三)舉一反三 加強版水王：找出出現次數剛好是一半的數字 分析：我們知道，水王問題：有N個數，其中有一個數出現超過一半，要求在線性時間求出這個數。那么，我的問題是，加強版水王：有N個數，其中有一個數剛好出現一半次數，要求在線性時間內求出這個數。 因為，很明顯，如果是剛好出現一半的話，如此例： 0，1，2，1 ： ~~~ 遍歷到0時，candidate為0，times為1 遍歷到1時，與candidate不同，times減為0 遍歷到2時，times為0，則candidate更新為2，times加1 遍歷到1時，與candidate不同，則times減為0；我們需要返回所保存candidate（數字2）的下一個數字，即數字1。 ~~~