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