一、题目：
现有一个灌水论坛，信息学院的学生都喜欢在上面交流灌水。传说在论坛上有一个“水王”，它不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目已超过了帖子数目的一半。
如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者ID在其中，请设计算法快速找到这个传说中的“水王”。
二、设计思路：
1、首先要快速找到，要求时间复杂度要低。如果进行ID数目多少排序的话，时间复杂度至少为O(n*lgn)，所以不能排序；
2、要想遍历一遍就能找到最多出现的ID，可以将数目少的ID删掉或屏蔽，那么剩下的就是要找的。因为题目中给出条件“该ID出现次数超过总和的一半”，所以，可两两连续比较，若不一样，则第一个ID置0，向后进行；若一样，则该数的计数器加1，最后输出计数器最大的ID。
三、源代码：
1 //找“水王”——胡亚宝——2015/04/21 2 3 #include "stdafx.h" 4 5 int _tmain(int argc, _TCHAR* argv[]) 6 { 7 int a[100],count[50]; 8 int len,max=0,flag; 9 printf("请输入元素个数："); 10 scanf("%d",&len); 11 printf("请输入各元素："); 12 for(int i=0;i<len;i++) 13 { 14 scanf("%d",&a[i]); 15 count[a[i]]=0; 16 } 17 18 for(int j=0;j<len-1;j++) 19 { 20 if(a[j]==a[j+1]) 21 { 22 count[a[j]]++; 23 if(count[a[j]]>max) 24 { 25 max=count[a[j]]; 26 flag=j; 27 } 28 } 29 30 if(a[j]!=a[j+1]) 31 { 32 a[j]=0; 33 } 34 } 35 36 printf("出现次数最多的元素为：%d ",a[flag]); 37 return 0; 38 }
四、运行结果：
五、心得体会：
首先我想出的解题思路是先排序，再查找，这样根据出现次数的多少排序以后，很容易就能找出“水王”。但此时时间复杂度不符合要求，还需要改进。
如果时间复杂度为O(n)，那么不能排序，一旦排序再去查找就要嵌套，所以要想出一个将所有的数遍历一遍就能找出的方法。此时有一个前提条件，就是该数出现的次数超过总次数，这样它和每一个数配对，最后总会剩下该数。所以可从第一个数开始，每一个数和它后面的数进行比较，若两数不相同，则可去除第一个数，第二个数接着与它后面的进行比较；若两数相同，那么该数的计数器加1。比到最后，一定是出现次数最多的数的计数器最大，那么此时输出该数。这样，只遍历一遍，就能找出该数。
这次的算法也是主要考察时间的优化，开始我只想到了消除，可是消除的条件还不是很明朗，通过老师的提醒，自己下课编写了算法和程序。对于这种优化算法的问题，还是应该多多练习。