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

winston

问题：
      原题叫“寻找发帖王”，其实就是在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)时间内找到这个数，再统计它出现的频率。这样就完美了！
      于是可以得到一个同解的跳跃式问题：检查一个数组中，是否存在一个数，它出现频率超过一半。