编程之美笔记 2.3 寻找发帖“水王”（数组中出现次数过半的元素）

Q: 某论坛有个水王，他发帖的数目超过了帖子总数的一半，如果你有这个论坛的所有帖子，且帖子作者ID也在表中，如何快速找到这个水王？

A:

解法一：

对所有的ID排序，扫描一遍排好序的ID列表，统计各ID的次数，超过一般的即是。

算法时间复杂度：O(NlogN+N) ，即排序加扫描时间。

解法二：

对ID排序，则第N/2项（从0开始编号）即是这个ID。

时间复杂度：O(NlogN+1)。

解法三：

思想：将大规模问题转化为等效的若干子问题，减小问题规模。

每次删除两个不同的ID，则剩下的ID列表中，水王的ID出现次数仍然超过一半。

时间复杂度：O(N)，只需要常数的额外内存。

TYPE find(TYPE *ID, int N)

{

         TYPE candidate;

         int nTimes, i;

         for(i=nTimes=0; i

         {

                   if(0==nTimes)

                   {

                            candidate = ID[i];

                            nTimes = 1;

                   }

                   else

                   {

                            if(candidate == ID[i])

                                     nTimes++;

                            else

                                     nTimes--;

                   }

         }

         return candidate;

}