[zz]

扩展问题

随着Tango的发展，管理员发现，“超级水王”没有了。统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？

参考上面的解法，思路如下：

如果每次删除四个不同的ID（不管是否包含发帖数目超过总数1/4的ID），那么，在剩下的ID列表中，原先发帖比例大于1/4的ID所占比例仍然大于1/4。可以通过不断重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得到问题的答案。

代码如下：

1 void Find(Type* ID, int N,Type candidate[3]) 2 { 3     Type ID_NULL;//定义一个不存在的ID 4     int nTimes[3], i; 5     nTimes[0]=nTimes[1]=nTimes[2]=0; 6     candidate[0]=candidate[1]=candidate[2]=ID_NULL; 7     for(i = 0; i < N; i++) 8     { 9         if(ID[i]==candidate[0])10         {11              nTimes[0]++;12         }13         else if(ID[i]==candidate[1])14         {15              nTimes[1]++;16         }17         else if(ID[i]==candidate[2])18         {19              nTimes[2]++;20         }21         else if(nTimes[0]==0)22         {23              nTimes[0]=1;24              candidate[0]=ID[i];25         }26         else if(nTimes[1]==0)27         {28              nTimes[1]=1;29              candidate[1]=ID[i];30         }31         else if(nTimes[2]==0)32         {33              nTimes[2]=1;34              candidate[2]=ID[i];35         }36         else37         {38              nTimes[0]--;39              nTimes[1]--;40              nTimes[2]--;41          }42     }43     return;44 }