编程之美----寻找发帖“水王”

时间：2014-11-09 23:33:10 收藏：0 阅读：365

题意：在一堆ID号中，有一个ID出现的次数大于总数的一半，如何快速找出那个ID。

我自己的想法是，如果ID号不是很大，用hash来存储每一个ID号出现的次数，出现一次，hash[ID]++，然后和max值比较，若大，则更新max值，复杂度为o(n)。

书上一个好的解法是：每次删除两个不同的ID(不管是否包含“水王"的ID)，那么在剩下的ID列表中，”水王“ID出现的次数仍然超过总数的一半，递归即可求解。复杂度为o(n)。

 1 int find(int ID[], int n)
 2 {
 3     int candicate,ntimes,i;
 4     for(i=ntimes=0;i<n;i++)
 5     {
 6         if(ntime==0)
 7         {
 8             candicate=ID[i];
 9             ntimes=1;
10         }
11         else 
12         {
13             if(candicate==ID[])
14                 ntimes++;
15             else 
16                 ntimes--;
17         }
18     }
19     return candicate;
20 }

View Code

原文：http://www.cnblogs.com/wen-ge/p/4086071.html