问题： 原题叫“寻找发帖王”，其实就是在n个数里，存在一个数x，出现频率超过n/2的数，要以最小的时间复杂度计算出这个x。
动机： 这个题目是昨晚无聊时，在CSDN论坛上看到的，起初我是这样想的：既然有个数x出现频率超过n/2，那如果排好序，那么第[n/2]个数一定就是x。这 样问题就规约为这样一个问题：“计算一组数的中位数”。《算法导论》有提出过解决办法，就是类似快速排序那样，使用分治算法，在O(n)复杂度内解决问 题。但算法性能依赖于数据的分布，最坏情况会达到O(n
2)。
后来在网上搜了一下，发现这居然是《编程之美》上的。记得当初上大学的时候，我还看过，可怎么也想不起来了。看到书上提到的算法，不禁黯然称奇！于是产生了个想法，我决定重新看一遍，并且写一个系列的博客，写下自己的心得。
引理： 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 - 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
夜风 阅读(2285)
评论(4) 编辑 收藏 引用 所属分类:
编程之美心得