题目：随着论坛的发展，管理员发现水王没有了，但是统计结果表明，有三个发帖很多的ID。据统计他们的发帖数量超过了1/4，你能从发帖列表中快速找到他们吗？
一、设计思路
如果按照先排序后查找的话，三个小水王则分别在1/4处，1/2处，3/4处，时间复杂度则为O（nlogn），不满足时间复杂度要求。参考上次找水王题目，每次消除两个不一样ID的帖子，则最后剩下的即是水王。此题可参照此方法，但一次要消除四个不同ID的帖子，消到最后，依旧是他们三个占据总数分别超过1/4。如此做法，虽然满足时间复杂度，但是空间复杂度略有提升。
二、源代码
#include<iostream.h> int main() { int ID[10]={1,2,3,4,1,2,3,1,2,3}; int ID_NULL;//定义一个不存在的ID int shui[3]; int flag[3]; int i; shui[0]=shui[1]=shui[2]=0; flag[0]=flag[1]=flag[2]=ID_NULL; for(i=0;i<10;i++) { if(ID[i]==flag[0]) { shui[0]++; } else if(ID[i]==flag[1]) { shui[1]++; } else if(ID[i]==flag[2]) { shui[2]++; } else if(shui[0]==0) { shui[0]=1; flag[0]=ID[i]; } else if(shui[1]==0) { shui[1]=1; flag[1]=ID[i]; } else if(shui[2]==0) { shui[2]=1; flag[2]=ID[i]; } else { shui[0]--; shui[1]--; shui[2]--; } } cout<<"小水王是："<<endl; cout<<flag[0]<<" "<<flag[1]<<" "<<flag[2]<<endl; return 0; }
三、运行结果
三、个人总结
这种题目并不是单纯地要求实现，而是要求我们运用算法来进行优化，减少程序运行时间，而这却需要编程人员耗费大量的脑力。找到对的解决方法就是解决这类问题的关键。
原文：http://www.cnblogs.com/benboerba/p/4461345.html