找水王

 

题目：

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。
如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？

思路：首先想到的是一个最直接的方法，我们可以队所有ID进行排序。然后再扫描一遍排好序的ID列表，统计各个ID出现的次数。如果某个ID出现的次数超过总数的一半，那么就输出这个ID。这个算法的时间复杂度为O(N*log2N+N)。如果一个ID出现的次数超过总数N的一半。那么，无论水王的ID是什么，这个有序的ID列表中的第N/2项（从0开始编号）一定会是这个ID（读者可以试着证明一下）。省去重新扫描一遍列表，可以节省一点算法耗费的时间。如果能够迅速定位到列表的某一项（比如使用数组来存储列表），除去排序的时间复杂度，后处理需要的时间为O（1）。如果每次删除两个不同的ID（不管是否包含“水王”的ID），那么，在剩下的ID列表中，“水王”ID出现的次数仍然超过总数的一半。看到这一点之后，就可以通过不断重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得到问题的答案。新的思路，避免了排序这个耗时的步骤，总的时间复杂度只有O（N），且只需要常数的额外内存。

#include <iostream>
using namespace std;  
  
int find (int *a, int N)  
{  
    int candiate;  
    int i, time;  
    for (i = time = 0; i < N; i++)  
    {  
        if (0 == time)  
        {  
            candiate = a[i];  
            time = 1;  
        }  
        else  
        {  
            if (candiate == a[i])  
            {  
                time++;  
            }  
            else  
            {  
                time--;  
            }  
        }  
    }  
    return candiate;  
}   
  
  
void main()  
{  
    int a[] = {1,2,3,4,5,8,2,3,4,1,6,12};  
    cout<<"水王是："<<find(a,12)<<endl;  
}