問(wèn)題： 原題叫“尋找發(fā)帖王”，其實(shí)就是在n個(gè)數(shù)里，存在一個(gè)數(shù)x，出現(xiàn)頻率超過(guò)n/2的數(shù)，要以最小的時(shí)間復(fù)雜度計(jì)算出這個(gè)x。
動(dòng)機(jī)： 這個(gè)題目是昨晚無(wú)聊時(shí)，在CSDN論壇上看到的，起初我是這樣想的：既然有個(gè)數(shù)x出現(xiàn)頻率超過(guò)n/2，那如果排好序，那么第[n/2]個(gè)數(shù)一定就是x。這 樣問(wèn)題就規(guī)約為這樣一個(gè)問(wèn)題：“計(jì)算一組數(shù)的中位數(shù)”。《算法導(dǎo)論》有提出過(guò)解決辦法，就是類(lèi)似快速排序那樣，使用分治算法，在O(n)復(fù)雜度內(nèi)解決問(wèn) 題。但算法性能依賴(lài)于數(shù)據(jù)的分布，最壞情況會(huì)達(dá)到O(n
2)。
后來(lái)在網(wǎng)上搜了一下，發(fā)現(xiàn)這居然是《編程之美》上的。記得當(dāng)初上大學(xué)的時(shí)候，我還看過(guò)，可怎么也想不起來(lái)了。看到書(shū)上提到的算法，不禁黯然稱(chēng)奇！于是產(chǎn)生了個(gè)想法，我決定重新看一遍，并且寫(xiě)一個(gè)系列的博客，寫(xiě)下自己的心得。
引理： n個(gè)數(shù)中，數(shù)x出現(xiàn)頻率超過(guò)n/2，那么從中去掉一對(duì)不相等的兩個(gè)數(shù)，x在剩下的(n-2)個(gè)數(shù)中的出現(xiàn)頻率依然超過(guò)n/2。
證明： 假設(shè)x出現(xiàn)了m次，則m > n/2，原頻率P0 = m/n > 1/2，從n個(gè)數(shù)中去掉一對(duì)不相同的兩個(gè)數(shù)<a, b>，有兩種情況：
- a != x, b != x。頻率P1 = m/(n-2) > m/n > 1/2
- a = x, b != x。 頻率P1 = (m - 1)/(n - 2)。P1 - P0 = (2m - n)/n(n - 2) > 0。則 P1 > P0 > 1/2
算法分析：
其實(shí)說(shuō)到底非常簡(jiǎn)單，就是在一堆數(shù)里隨便拿一個(gè)數(shù)，再找一個(gè)與它不相等的，然后一起扔掉，這樣問(wèn)題規(guī)模不斷縮小，最終等到找不到一個(gè)不相等的數(shù)時(shí)，就成功 了。但要簡(jiǎn)化算法，就不能每拿一個(gè)數(shù)就統(tǒng)統(tǒng)找一遍。可以考慮準(zhǔn)備一個(gè)隊(duì)列，隊(duì)列里放著暫時(shí)扔不掉的數(shù)。如從頭開(kāi)始，將a[0]放入隊(duì)列，再看a[1]，如 果a[0] != a[1]，則扔掉a[1]和a[0]，a[0]從隊(duì)列取出；如果a[0] == a[1]，則a[1]入隊(duì)列，然后a[2]進(jìn)行相同的操作，以此類(lèi)推。
解法依然可以?xún)?yōu)化。顯而易見(jiàn)，隊(duì)列里所有的數(shù)總是全部相等的，既然相等就沒(méi)有必要存入隊(duì)列，只要知道：1.假想的隊(duì)列里的數(shù)什么 2.隊(duì)列的長(zhǎng)度。
這樣就得到了《編程之美》中的代碼了：
1 int data_more_than_half(const int arr[], const size_t size) {
2 int candidate;
3 int count = 0;
4
5 for(size_t i = 0; i < size; i++) {
6 if (count == 0) {
7 candidate = arr[i];
8 count = 1;
9 }
10 else {
11 if (candidate == arr[i]) {
12 count++;
13 }
14 else {
15 count--;
16 }
17 }
18 }
19 return candidate;
20 }
應(yīng)用：
代碼看似簡(jiǎn)單，但我感到意猶未盡，正回味著，突然想到一個(gè)問(wèn)題：如果條件（存在一個(gè)出現(xiàn)頻率超過(guò)一半的數(shù)）不滿足，那會(huì)出現(xiàn)什么情況？如何避免呢？
很顯然，我們的解法就是基于這樣一個(gè)條件的，一旦條件不滿足，得到的數(shù)就沒(méi)有任何意義。但不難發(fā)現(xiàn)，避免問(wèn)題的出現(xiàn)也非常簡(jiǎn)單：驗(yàn)證找到的數(shù)是否出現(xiàn)頻率超過(guò)一半。
這也是個(gè)常用的方法：假設(shè)檢驗(yàn)法。
對(duì)于一個(gè)數(shù)組，假設(shè)存在一個(gè)數(shù)，它出現(xiàn)頻率超過(guò)一半。然后在O(n)時(shí)間內(nèi)找到這個(gè)數(shù)，再統(tǒng)計(jì)它出現(xiàn)的頻率。這樣就完美了！
于是可以得到一個(gè)同解的跳躍式問(wèn)題：檢查一個(gè)數(shù)組中，是否存在一個(gè)數(shù)，它出現(xiàn)頻率超過(guò)一半。
posted on 2012-05-23 00:39
夜風(fēng) 閱讀(2341)
評(píng)論(4) 編輯 收藏 引用 所屬分類(lèi):
編程之美心得