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

分析：這是一道廣為流傳的面試題，包括百度、微軟和Google在內的多家公司都曾經采用過這個題目。要幾十分鐘的時間里很好地解答這道題，除了較好的編程能力之外，還需要較快的反應和較強的邏輯思維能力。

看到這道題，我們馬上就會想到，要是這個數組是排序的數組就好了。如果是排序的數組，那么我們只要遍歷一次就可以統計出每個數字出現的次數，這樣也就能找出符合要求的數字了。題目給出的數組沒有說是排好序的，因此我們需要給它排序。排序的時間復雜度是O(nlogn)，再加上遍歷的時間復雜度O(n)，因此總的復雜度是O(nlogn)。

接下來我們試著看看能不能想出更快的算法。前面思路的時間主要是花在排序上。我們可以創建一個哈希表來消除排序的時間。哈希表的鍵值（Key）為數組中的數字，值（Value）為該數字對應的次數。有了這個輔助的哈希表之后，我們只需要遍歷數組中的每個數字，找到它在哈希表中對應的位置并增加它出現的次數。這種哈希表的方法在數組的所有數字都在一個比較窄的范圍內的時候很有效。本博客系列的第13題就是一個應用哈希表的例子。不過本題并沒有限制數組里數字的范圍，我們要么需要創建一個很大的哈希表，要么需要設計一個很復雜的方法來計算哈希值。因此總體說來這個方法還不是很好。

前面兩種思路都沒有考慮到題目中數組的特性：數組中有個數字出現的次數超過了數組長度的一半。也就是說，有個數字出現的次數比其他所有數字出現次數的和還要多。因此我們可以考慮在遍歷數組的時候保存兩個值：一個是數組中的一個數字，一個是次數。當我們遍歷到下一個數字的時候，如果下一個數字和我們之前保存的數字相同，則次數加1。如果下一個數字和我們之前保存的數字不同，則次數減1。如果次數為零，我們需要保存下一個數字，并把次數設為1。由于我們要找的數字出現的次數比其他所有數字出現的次數之和還要多，那么要找的數字肯定是最后一次把次數設為1時對應的數字。

基于這個思路，我們不難寫出如下代碼：

bool g_bInputInvalid = false;// // Input: an array with "length" numbers. A number in the array // appear more than "length / 2 + 1" times. // Output: If the input is valid, return the number appearing more than // "length / 2 + 1" times. Otherwise, return 0 and set flag g_bInputInvalid // to be true. // int MoreThanHalfNum(int* numbers, unsigned int length) {if(numbers == NULL && length == 0){g_bInputInvalid = true;return 0;}g_bInputInvalid = false;int result = numbers[0];int times = 1;for(int i = 1; i < length; ++i){if(times == 0){result = numbers[i];times = 1;}else if(numbers[i] == result)times++;elsetimes--;}// verify whether the input is validtimes = 0;for(int i = 0; i < length; ++i){if(numbers[i] == result)times++;}if(times * 2 <= length){g_bInputInvalid = true;result = 0;}return result; }

?

???????在上述代碼中，有兩點值得討論：

（1）??????我們需要考慮當輸入的數組或者長度無效時，如何告訴函數的調用者輸入無效。關于處理無效輸入的幾種常用方法，在本博客系列的第17題中有詳細的討論；

（2）??????本算法的前提是輸入的數組中的確包含一個出現次數超過數組長度一半的數字。如果數組中并不包含這么一個數字，那么輸入也是無效的。因此在函數結束前我還加了一段代碼來驗證輸入是不是有效的。

?

本文已經收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動，書中的分析講解更加詳細。歡迎關注。

本題已被九度Online Judge系統收錄，歡迎讀者移步到http://ac.jobdu.com/hhtproblems.php在線測試自己的代碼。

博主何海濤對本博客文章享有版權。網絡轉載請注明出處http://zhedahht.blog.163.com/。整理出版物請和作者聯系。對解題思路有任何建議，歡迎在評論中告知，或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht與我討論。謝謝。

總結

以上是生活随笔為你收集整理的程序员面试题精选100题(47)-数组中出现次数超过一半的数字[算法]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。