題目描述

題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個(gè)數(shù)字。

分析與解法

一個(gè)數(shù)組中有很多數(shù)，現(xiàn)在我們要找出其中那個(gè)出現(xiàn)次數(shù)超過總數(shù)一半的數(shù)字，怎么找呢？大凡當(dāng)我們碰到某一個(gè)雜亂無序的東西時(shí)，我們?nèi)说膬?nèi)心本質(zhì)期望是希望把它梳理成有序的。所以，我們得分兩種情況來討論，無序和有序。

解法一

如果無序，那么我們是不是可以先把數(shù)組中所有這些數(shù)字先進(jìn)行排序（至于排序方法可選取最常用的快速排序）。排完序后，直接遍歷，在遍歷整個(gè)數(shù)組的同時(shí)統(tǒng)計(jì)每個(gè)數(shù)字的出現(xiàn)次數(shù)，然后把那個(gè)出現(xiàn)次數(shù)超過一半的數(shù)字直接輸出，題目便解答完成了。總的時(shí)間復(fù)雜度為O(nlogn + n)。

但如果是有序的數(shù)組呢，或者經(jīng)過排序把無序的數(shù)組變成有序后的數(shù)組呢？是否在排完序O(nlogn)后，還需要再遍歷一次整個(gè)數(shù)組？

我們知道，既然是數(shù)組的話，那么我們可以根據(jù)數(shù)組索引支持直接定向到某一個(gè)數(shù)。我們發(fā)現(xiàn)，一個(gè)數(shù)字在數(shù)組中的出現(xiàn)次數(shù)超過了一半，那么在已排好序的數(shù)組索引的N/2處（從零開始編號(hào)），就一定是這個(gè)數(shù)字。自此，我們只需要對(duì)整個(gè)數(shù)組排完序之后，然后直接輸出數(shù)組中的第N/2處的數(shù)字即可，這個(gè)數(shù)字即是整個(gè)數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字，總的時(shí)間復(fù)雜度由于少了最后一次整個(gè)數(shù)組的遍歷，縮小到O(n*logn)。

然時(shí)間復(fù)雜度并無本質(zhì)性的改變，我們需要找到一種更為有效的思路或方法。

解法二

既要縮小總的時(shí)間復(fù)雜度，那么可以用查找時(shí)間復(fù)雜度為O(1)的hash表，即以空間換時(shí)間。哈希表的鍵值（Key）為數(shù)組中的數(shù)字，值（Value）為該數(shù)字對(duì)應(yīng)的次數(shù)。然后直接遍歷整個(gè)hash表，找出每一個(gè)數(shù)字在對(duì)應(yīng)的位置處出現(xiàn)的次數(shù)，輸出那個(gè)出現(xiàn)次數(shù)超過一半的數(shù)字即可。

解法三

Hash表需要O(n)的空間開銷，且要設(shè)計(jì)hash函數(shù)，還有沒有更好的辦法呢？我們可以試著這么考慮，如果每次刪除兩個(gè)不同的數(shù)（不管是不是我們要查找的那個(gè)出現(xiàn)次數(shù)超過一半的數(shù)字），那么，在剩下的數(shù)中，我們要查找的數(shù)（出現(xiàn)次數(shù)超過一半）出現(xiàn)的次數(shù)仍然超過總數(shù)的一半。通過不斷重復(fù)這個(gè)過程，不斷排除掉其它的數(shù)，最終找到那個(gè)出現(xiàn)次數(shù)超過一半的數(shù)字。這個(gè)方法，免去了排序，也避免了空間O(n)的開銷，總得說來，時(shí)間復(fù)雜度只有O(n)，空間復(fù)雜度為O(1)，貌似不失為最佳方法。

舉個(gè)簡(jiǎn)單的例子，如數(shù)組a[5] = {0, 1, 2, 1, 1};

很顯然，若我們要找出數(shù)組a中出現(xiàn)次數(shù)超過一半的數(shù)字，這個(gè)數(shù)字便是1，若根據(jù)上述思路4所述的方法來查找，我們應(yīng)該怎么做呢？通過一次性遍歷整個(gè)數(shù)組，然后每次刪除不相同的兩個(gè)數(shù)字，過程如下簡(jiǎn)單表示：

0?1?2?1?1?=>2?1?1=>1

最終1即為所找。

但是數(shù)組如果是{5, 5, 5, 5, 1}，還能運(yùn)用上述思路么？很明顯不能，咱們得另尋良策。

解法四

更進(jìn)一步，考慮到這個(gè)問題本身的特殊性，我們可以在遍歷數(shù)組的時(shí)候保存兩個(gè)值：一個(gè)candidate，用來保存數(shù)組中遍歷到的某個(gè)數(shù)字；一個(gè)nTimes，表示當(dāng)前數(shù)字的出現(xiàn)次數(shù)，其中，nTimes初始化為1。當(dāng)我們遍歷到數(shù)組中下一個(gè)數(shù)字的時(shí)候：

• 如果下一個(gè)數(shù)字與之前candidate保存的數(shù)字相同，則nTimes加1；

• 如果下一個(gè)數(shù)字與之前candidate保存的數(shù)字不同，則nTimes減1；

• 每當(dāng)出現(xiàn)次數(shù)nTimes變?yōu)?后，用candidate保存下一個(gè)數(shù)字，并把nTimes重新設(shè)為1。 直到遍歷完數(shù)組中的所有數(shù)字為止。

舉個(gè)例子，假定數(shù)組為{0, 1, 2, 1, 1}，按照上述思路執(zhí)行的步驟如下：

• 1.開始時(shí)，candidate保存數(shù)字0，nTimes初始化為1；

• 2.然后遍歷到數(shù)字1，與數(shù)字0不同，則nTimes減1變?yōu)?；

• 3.因?yàn)閚Times變?yōu)榱?，故candidate保存下一個(gè)遍歷到的數(shù)字2，且nTimes被重新設(shè)為1；

• 4.繼續(xù)遍歷到第4個(gè)數(shù)字1，與之前candidate保存的數(shù)字2不同，故nTimes減1變?yōu)?；

• 5.因nTimes再次被變?yōu)榱?，故我們讓candidate保存下一個(gè)遍歷到的數(shù)字1，且nTimes被重新設(shè)為1。最后返回的就是最后一次把nTimes設(shè)為1的數(shù)字1。

思路清楚了，完整的代碼如下：

//a代表數(shù)組，length代表數(shù)組長度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++;????????????elsenTimes--;}}????return?candidate; }

即針對(duì)數(shù)組{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；......

舉一反三

加強(qiáng)版水王：找出出現(xiàn)次數(shù)剛好是一半的數(shù)字

分析：我們知道，水王問題：有N個(gè)數(shù)，其中有一個(gè)數(shù)出現(xiàn)超過一半，要求在線性時(shí)間求出這個(gè)數(shù)。那么，我的問題是，加強(qiáng)版水王：有N個(gè)數(shù)，其中有一個(gè)數(shù)剛好出現(xiàn)一半次數(shù)，要求在線性時(shí)間內(nèi)求出這個(gè)數(shù)。

因?yàn)?#xff0c;很明顯，如果是剛好出現(xiàn)一半的話，如此例： 0，1，2，1 ：

遍歷到0時(shí)，candidate為0，times為1 遍歷到1時(shí)，與candidate不同，times減為0 遍歷到2時(shí)，times為0，則candidate更新為2，times加1 遍歷到1時(shí)，與candidate不同，則times減為0；我們需要返回所保存candidate（數(shù)字2）的下一個(gè)數(shù)字，即數(shù)字1。

總結(jié)

以上是生活随笔為你收集整理的出现次数超过一半的数字的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。