2.3 寻找发帖水王

题目：水王发帖的数量超过总贴数的一半，已知所有帖子的发帖ID列表，请快速找出水王ID

思路：除了最为直观的排序法+遍历外，突破口在发帖总数超一半的这个点上。水王id和其它的id可以相互抵消，最后留下的肯定是水王的id。只需要O(n)。

 1 int findHalfId(const int ids[],int len){
 2 
 3     int i,candidate,nTimes;
 4     for(i=candidate=nTimes=0;i<len;i++){
 5         
 6         if(nTimes==0){
 7             candidate = ids[i];
 8             nTimes=1;
 9         }else{
10             if(candidate==ids[i]){
11                 nTimes++;
12             }else{
13                 nTimes--;
14             }
15         }
16     }
17 
18     return candidate;
19 }

扩展：有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？

这个扩展问题虽也是使用上述的思路，但是有三个id，关键地方在于，这三个id并不互相抵消，而是合力“对付”其余的id。因此当遍历到有id不等于这三个id时，这三个id的nTimes都需要-1。

打个比喻，上面的水王超过1/2，所以他一个人独自“对付”剩下的少于1/2，留下的就是他；现在三个水王各超过1/4，所以合力“对付”剩下的少于1/4，留下的就是这三个Id。

 1 int findQuarterId(const int ids[],int len){
 2     int nTimes[3], i;
 3     nTimes[0]=nTimes[1]=nTimes[2]=0;
 4     int candidate[3];
 5     candidate[0]=candidate[1]=candidate[2]=0;
 6     for(i = 0; i < len; i++)
 7     {
 8         if(ids[i]==candidate[0])
 9         {
10              nTimes[0]++;
11         }
12         else if(ids[i]==candidate[1])
13         {
14              nTimes[1]++;
15         }
16         else if(ids[i]==candidate[2])
17         {
18              nTimes[2]++;
19         }
20         else if(nTimes[0]==0)
21         {
22              nTimes[0]=1;
23              candidate[0]=ids[i];
24         }
25         else if(nTimes[1]==0)
26         {
27              nTimes[1]=1;
28              candidate[1]=ids[i];
29         }
30         else if(nTimes[2]==0)
31         {
32              nTimes[2]=1;
33              candidate[2]=ids[i];
34         }
35         else
36         {
37              nTimes[0]--;
38              nTimes[1]--;
39              nTimes[2]--;
40          }
41     }
42     return candidate[3];
43 }