找水王问题

一、题目

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。

如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？

二、设计思路

课上老师给出了“消消乐”思路，根据这个思路，将ID存入一个数组中，从第一个开始与后面的比较，不相同则“消去”，因为水王的ID出现次数超过一半，所以消去后剩下的ID就是水王的ID。课上与同学讨论的的方法是用一个变量来计数以实现“消除”。

三、代码

 1 #include <iostream.h>
 2  
 3  int main()
 4  {
 5      int a[100];
 6      int i,j,k=1;
 7      int shui;
 8      cout<<"假设有10个ID，";
 9      for(i=0;i<10;i++)
10      {
11          cout<<"请输入第"<<i+1<<"个ID："<<endl;
12          cin>>a[i];
13      }
14      shui=a[0];
15      for(i=1;i<10;i++)
16      {
17          if(shui!=a[i])
18          {
19              k=k-1;
20              if(k<0)
21              {
22                  shui=a[i+1];
23                  k=1;
24                  i++;
25              }
26          }
27          else
28          {
29              shui=a[i];
30              k=k+1;
31          }
32      }
33      cout<<"水王的ID是："<<shui<<endl;
34      return 0;
35  }

四、运行结果截图

五、总结

这道题继续是优化问题，如果通过遍历计数，比较所有出现的ID数目找出最多的也可实现，但时间复杂度高，不是最优算法。算法优化有很长的路，应该多想好的方法，平时编写也该注意寻找更优的算法。