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