寻找发帖“水王”

kon3155

根据《编程之美》——寻找发帖“水王” 改编

传说，数学研发论坛有一大“水王”（大家都知道是谁 ） ，他不但喜欢发贴，还会回复其他 ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的 ID也在表中，你能快速找出这个传说中的水王吗？

【分析与解法】
首先想到的是一个最直接的方法，我们可以对所有 ID进行排序。然后再扫描一遍排好序的 ID列表，统计各个 ID出现的次数。如果某个 ID出现的次数超过总数的一半，那么就输出这个 ID。这个算法的时间复杂度为 O（N * log2N + N）。 如果ID列表已经是有序的，还需要扫描一遍整个列表来统计各个ID出现的次数吗？
如果一个 ID 出现的次数超过总数 N 的一半。那么，无论水王的 ID 是什么，这个有序的 ID列表中的第 N/2 项（从 0 开始编号）一定会是这个 ID（读者可以试着证明一下）。省去重新扫描一遍列表， 可以节省一点算法耗费的时间。 如果能够迅速定位到列表的某一项 （比如使用数组来存储列表），除去排序的时间复杂度，后处理需要的时间为 O（1）。 但上面两种方法都需要先对 ID列表进行排序，时间复杂度方面没有本质的改进。能否避免排序呢？

如果每次删除两个不同的 ID（不管是否包含“水王”的 ID），那么，在剩下的 ID列表中，“水王”ID出现的次数仍然超过总数的一半。 看到这一点之后， 就可以通过不断重复这个过程，把 ID 列表中的 ID 总数降低（转化为更小的问题），从而得到问题的答案。新的思路，避免了排序这个耗时的步骤，总的时间复杂度只有 O（N），且只需要常数的额外内存。伪代码如下：

1. Type Find(Type* ID, int N)
   
2. {
   
3.     Type candidate;
   
4.     int nTimes, i;
   
5.     for(i = nTimes = 0; i < N; i++)
   
6.     {
   
7.         if(nTimes == 0)
   
8.         {
   
9.             candidate = ID[i], nTimes = 1;
   
10.         }
    
11.         else
    
12.         {
    
13.             if(candidate == ID[i])
    
14.             nTimes++;
    
15.             else
    
16.             nTimes--;
    
17.         }
    
18.     }
    
19.     return candidate;
    
20. }

复制代码

在这个题目中，有一个计算机科学中很普遍的思想，就是如何把一个问题转化为规模较小的若干个问题。分治、递推和贪心等都是基于这样的思路。在转化过程中，小的问题跟原问题本质上一致。这样，我们可以通过同样的方式将小问题转化为更小的问题。因此，转化过程是很重要的。像上面这个题目，我们保证了问题的解在小问题中仍然具有与原问题相同的性质：水王的 ID 在 ID 列表中的次数超过一半。转化本身计算的效率越高，转化之后问题规模缩小得越快，则整体算法的时间复杂度越低。

【问题】
随着数学研发论坛的发展，管理员发现，“超级水王”没有了。统计结果表明，有 3 个发帖很多的 ID（大家也都知道，嚎），他们的发帖数目都超过了帖子总数目 N的 1/4。你能从发帖 ID列表中快速找出他们的ID吗？

gxqcn

里面阐述的算法思路蛮巧妙的。

无心人

关键是取得ID的算法
相对来说分析倒是很简单的

wayne

C能获取emath上的数据吗

无心人

应该能，只要能有函数枚举论坛帖子的数据

wayne

原帖由 无心人 于 2009-3-17 11:56 发表
应该能，只要能有函数枚举论坛帖子的数据

强，那我重点关注一下这个主题的进展

mathe

找一个wget的源代码吧

wayne

原帖由 mathe 于 2009-3-17 16:26 发表
找一个wget的源代码吧

明白了。
强！

kon3155

搜了一个解答作为参考，来自http://hi.baidu.com/azuryy/blog/ ... 3c7ac151da4b15.html

1. Type candidate1;
   
2. Type candidate2;
   
3. Type candidate3;
   
4. 
   
5. void Find(Type* ID,  int N)
   
6. {
   
7.     int nTimes1 = 0 ;
   
8.     int nTimes2 = 0 ;
   
9.     int nTimes3 = 0 ;
   
10.     int i;
    
11. 
    
12.     for( i = 0; i < N; i++)
    
13.     {
    
14.         if (nTimes1 == 0)
    
15.         {
    
16.             candidate1 = ID[i], nTimes1 = 1;
    
17.         }
    
18.         else
    
19.         {
    
20.             if (candidate1 == ID[i])
    
21.             {
    
22.                 nTimes1++;
    
23.             }
    
24.             else
    
25.             {
    
26.                 if (nTimes2 == 0)
    
27.                 {
    
28.                     candidate2 = ID[i], nTimes2 = 1;
    
29.                 }
    
30.                 else
    
31.                 {
    
32.                     if (candidate2 == ID[i])
    
33.                     {
    
34.                         nTimes2++;
    
35.                     }
    
36.                     else
    
37.                     {
    
38.                         if (nTimes3 == 0)
    
39.                         {
    
40.                             candidate3 = ID[i], nTimes3 = 1;
    
41.                         }
    
42.                         else
    
43.                         {
    
44.                             if (candidate3 == ID[i])
    
45.                             {
    
46.                                 nTimes3++;
    
47.                             }
    
48.                             else
    
49.                             {
    
50.                                 nTimes1--;
    
51.                                 nTimes2--;
    
52.                                 nTimes3--;
    
53.                             }
    
54.                         }
    
55.                     }
    
56.                 }
    
57.             }
    
58.         }
    
59.     }
    
60. }
    
61. 
    
62. int main()
    
63. {
    
64.     int a[] = {0,4,1,4,0,4,1,4,1,0,3,3,0,3,3,3};
    
65.     Find(a, 16);
    
66.     cout << candidate1 << " " << candidate2 << " " << candidate3 << endl;
    
67.     return 0;
    
68. }

复制代码

看代码就明白了，其实思想是一样的。

kon3155

我想对于一个百度的面试题：
有一个很大的log文件，里面记录的是用户搜索的关键字，现在的要求是，统计被搜索最频繁的前10个关键字

用这个方法的话，时间和额外空间都应该不错了吧。

当然换成switch代码可读性要好一些。