ACE Developer

 找回密码
 用户注册

QQ登录

只需一步,快速开始

查看: 5232|回复: 0

编程之美----寻找出现频率超过一半的数

[复制链接]
发表于 2012-5-23 21:18:56 | 显示全部楼层 |阅读模式
问题:
      原题叫“寻找发帖王”,其实就是在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>,有两种情况:

  • 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 - 1) > 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. 1 int data_more_than_half(const int arr[], const size_t size) {
  2. 2     int candidate;
  3. 3     int count = 0;
  4. 4
  5. 5     for(size_t i = 0; i < size; i++) {
  6. 6         if (count == 0) {
  7. 7             candidate = arr[i];
  8. 8             count = 1;
  9. 9         }
  10. 10         else {
  11. 11             if (candidate == arr[i]) {
  12. 12                 count++;
  13. 13             }
  14. 14             else {
  15. 15                 count--;
  16. 16             }
  17. 17         }
  18. 18     }
  19. 19     return candidate;
  20. 20 }
复制代码


应用:
      代码看似简单,但我感到意犹未尽,正回味着,突然想到一个问题:如果条件(存在一个出现频率超过一半的数)不满足,那会出现什么情况?如何避免呢?
      很显然,我们的解法就是基于这样一个条件的,一旦条件不满足,得到的数就没有任何意义。但不难发现,避免问题的出现也非常简单:验证找到的数是否出现频率超过一半。
      这也是个常用的方法:假设检验法。
      对于一个数组,假设存在一个数,它出现频率超过一半。然后在O(n)时间内找到这个数,再统计它出现的频率。这样就完美了!
      于是可以得到一个同解的跳跃式问题:检查一个数组中,是否存在一个数,它出现频率超过一半。


您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

Archiver|手机版|小黑屋|ACE Developer ( 京ICP备06055248号 )

GMT+8, 2022-9-27 19:09 , Processed in 0.009589 second(s), 6 queries , Redis On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表