出現次數超過一半的數（面試題）

出現次數超過一半的數

題目描述

數組中有一個數出現的次數超過了數組長度的一半，找出這個數。

分析與解法

因為不确定給定的數組是無序還是有序的，是以要分情況讨論。

解法一：排序

如果給定的數組是無序的，那麼可以先對數組進行排序（至于排序方法可選取最常用的快速排序）。排完序後周遊數組，在周遊整個數組的同時統計每個數的出現次數，然後把那個出現次數超過一半的數直接輸出，題目便算解答完了。總的時間複雜度為O(nlogn+n)。

但是，如果給定的數組是有序的，或者經過排序後把無序的數組變成有序的之後，是否還需要再周遊一次數組，以統計每個數出現的次數呢？

實際上，如果某個數在數組中的出現次數超過一半，那麼在已經排好序的數組索引的 n/2 處（從零開始編号）就一定是要我的這個數。是以，對整個數組排完序之後，隻需要直接輸出數組中的第n/2處的數即可，這個數即是整個數組中出現次數超過一半的數，總的時間複雜度由于少了最後一次整個數組的周遊，而降到O(nlogn)。

然而，時間複雜度從O(nlogn+n)降到O(nlogn)并無本質上的改變，我們需要找到一種更有效的思路或方法。

解法二：散清單

通常來說，要想降低時間複雜度，有這麼幾個思路可以選擇。

·減少不必要的操作，比如解法一中數組排完序後可以直接輸出第n/2處的那個數，不必再統計每個數的出現次數。

·以空間換時間，比如借助散清單達到快速映射的目的。

應根據問題本身的特性使用對應的技巧。比如在KMP算法中，通過對模式串的預處理求解出next數組，而後比對失敗時直接查next數組便可得到下一次比對的位置。

針對以空間換時間，我們自然而然想到了查找時間複雜度為O(1)的散清單。首先用散清單完成數組中每個數出現次數的統計，其中，散清單的鍵為數組中的數，值為該數出現的次數。這樣，利用散清單完成統計後，如果需要找出那個出現次數超過一半的數，直接周遊整個散清單，然後輸出該數即可。

構照叙清單後，查一次的時間複雜度為O(1)，周遊一遍查詢n次，則總的時間複雜度為O(1)。但是，散清單的方法需要O(n)的空間開銷，且要設計散列函數，還有沒有更好的辦法呢？

解法三：每次删除兩個不同的數

根據這個問題本身的特殊性，可以試着這麼考慮，通過每次删除兩個不同的數（不管是不是我們要查找的那個出現次數超過一半的數），在剩下的數中，我們要查找的數的出現次數仍将會超過剩餘總數的一半。通過不斷重複這個過程，不斷排除掉其他的數，最終找到那個出現次數超過一半的數。總的說來，時間複雜度隻有O(n)，空間複雜度為O(1)，免去了排序，也避免了O(n)的空間開銷。

舉個簡單的例子，如數組a[5]={0, 1, 2, 1, 1}。很顯然，若要找出數組a中出現次數超過一半的數，這個數便是1。通過一次性周遊整個數組，然後每次删除不相同的兩個數，過程簡單表示如下。

（1）給定序列0, 1, 2, 1, 1。

（2）删除不相同的兩個數0和1，序列變為2, 1, 1。

（3）最後再删去兩個不同的數2和1，序列變為1。

（4）最終1即為所要找的結果。

解法四：記錄兩個值

更進一步，我們可以在周遊數組的時候儲存兩個值：一個是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。

（6）最後傳回的就是最後一次把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}執行上述程式後，candidate和nTimes等相關變量的變化如表4-1所示。

表4-1

舉一反三

出現次數剛好是一半的數

有n個數，其中有一個數剛好出現一半次數，要求線上性時間内求出這個數。

點評：如果是剛好出現一半，如此例的{0, 1, 2, 1}，開始時，candidate儲存數0，nTimes初始化為1；周遊到1時，與candidate不同，nTimes減為0；周遊到2時，因nTimes為0，故candidate更新為2，nTimes重新設為1；周遊到1後，與之前candidate儲存的數2不同，則nTimes減為0；最終傳回candidate所儲存數（2）的下一個數1。

問題擴充

給定一個有限集合U，S1, S2,…, Sn都是U的非空子集，且它們滿足任意多個集合的并集仍然在這些集合裡。請證明：一定存在某一個元素，存在于至少一半的集合裡。