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