問題：
      原題叫“尋找發(fā)帖王”，其實就是在n個數(shù)里，存在一個數(shù)x，出現(xiàn)頻率超過n/2的數(shù)，要以最小的時間復雜度計算出這個x。

動機：
      這個題目是昨晚無聊時，在CSDN論壇上看到的，起初我是這樣想的：既然有個數(shù)x出現(xiàn)頻率超過n/2，那如果排好序，那么第[n/2]個數(shù)一定就是x。這 樣問題就規(guī)約為這樣一個問題：“計算一組數(shù)的中位數(shù)”?！端惴▽д摗酚刑岢鲞^解決辦法，就是類似快速排序那樣，使用分治算法，在O(n)復雜度內(nèi)解決問 題。但算法性能依賴于數(shù)據(jù)的分布，最壞情況會達到O(n²)。
      后來在網(wǎng)上搜了一下，發(fā)現(xiàn)這居然是《編程之美》上的。記得當初上大學的時候，我還看過，可怎么也想不起來了?？吹綍咸岬降乃惴ǎ唤鋈环Q奇！于是產(chǎn)生了個想法，我決定重新看一遍，并且寫一個系列的博客，寫下自己的心得。

引理：
      n個數(shù)中，數(shù)x出現(xiàn)頻率超過n/2，那么從中去掉一對不相等的兩個數(shù)，x在剩下的(n-2)個數(shù)中的出現(xiàn)頻率依然超過n/2。

證明：
      假設x出現(xiàn)了m次，則m > n/2，原頻率P0 = m/n > 1/2，從n個數(shù)中去掉一對不相同的兩個數(shù)<a, b>，有兩種情況：

1. a != x, b != x。頻率P1 = m/(n-2) > m/n > 1/2
   
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.隊列的長度。

      這樣就得到了《編程之美》中的代碼了：

應用：

      代碼看似簡單，但我感到意猶未盡，正回味著，突然想到一個問題：如果條件（存在一個出現(xiàn)頻率超過一半的數(shù)）不滿足，那會出現(xiàn)什么情況？如何避免呢？

      很顯然，我們的解法就是基于這樣一個條件的，一旦條件不滿足，得到的數(shù)就沒有任何意義。但不難發(fā)現(xiàn)，避免問題的出現(xiàn)也非常簡單：驗證找到的數(shù)是否出現(xiàn)頻率超過一半。

      這也是個常用的方法：假設檢驗法。

      對于一個數(shù)組，假設存在一個數(shù)，它出現(xiàn)頻率超過一半。然后在O(n)時間內(nèi)找到這個數(shù)，再統(tǒng)計它出現(xiàn)的頻率。這樣就完美了！

      于是可以得到一個同解的跳躍式問題：檢查一個數(shù)組中，是否存在一個數(shù)，它出現(xiàn)頻率超過一半。