posts - 4,  comments - 27,  trackbacks - 0
问题:
      原题叫“寻找发帖王”,其实就是在n个数里,存在一个数x,出现频率超过n/2的数,要以最小的时间复杂度计算出这个x。

动机:
      这个题目是昨晚无聊时,在CSDN论坛上看到的,起初我是这样想的:既然有个数x出现频率超过n/2,那如果排好序,那么第[n/2]个数一定就是x。这 样问题就规约为这样一个问题:“计算一组数的中位数”。《算法导论》有提出过解决办法,就是类似快速排序那样,使用分治算法,在O(n)复杂度内解决问 题。但算法性能依赖于数据的分布,最坏情况会达到O(n2)。
      后来在网上搜了一下,发现这居然是《编程之美》上的。记得当初上大学的时候,我还看过,可怎么也想不起来了。看到书上提到的算法,不禁黯然称奇!于是产生了个想法,我决定重新看一遍,并且写一个系列的博客,写下自己的心得。

引理:
      n个数中,数x出现频率超过n/2,那么从中去掉一对不相等的两个数,x在剩下的(n-2)个数中的出现频率依然超过n/2。

证明:
      假设x出现了m次,则m > n/2,原频率P0 = m/n > 1/2,从n个数中去掉一对不相同的两个数<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

算法分析:

      其实说到底非常简单,就是在一堆数里随便拿一个数,再找一个与它不相等的,然后一起扔掉,这样问题规模不断缩小,最终等到找不到一个不相等的数时,就成功 了。但要简化算法,就不能每拿一个数就统统找一遍。可以考虑准备一个队列,队列里放着暂时扔不掉的数。如从头开始,将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 夜风 阅读(2211) 评论(4)  编辑 收藏 引用 所属分类: 编程之美心得

FeedBack:
# re: 编程之美----寻找出现频率超过一半的数[未登录]
2012-05-23 09:31 | ithaca
看来你还没整明白count是干什么用的。。。  回复  更多评论
  
# re: 编程之美----寻找出现频率超过一半的数[未登录]
2012-05-23 13:16 | yefeng
@ithaca
我的解释有什么问题吗?  回复  更多评论
  
# re: 编程之美----寻找出现频率超过一半的数[未登录]
2012-05-23 14:34 | 春秋十二月
在《算法引论》中查找众数一节,讲解了这种线性时间算法的实现,不管众数是否存在。提个小问题,P1 - P0 = (2m - n)/n(n - 1) > 0,分母应该是n(n-2)吧  回复  更多评论
  
# re: 编程之美----寻找出现频率超过一半的数[未登录]
2012-05-23 19:42 | yefeng
@春秋十二月
手误,确实是n(n-2)  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年5月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(1)

随笔分类(7)

随笔档案(4)

文章分类

最新评论

阅读排行榜

评论排行榜