课堂练习之《找水王》

实验题目：

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？

实现思路：

起初的思想则是把所有的ID进行排序，找到中间的那个ID一定就是水王（前提是水王树木超过了一半，而且水王存在），但是这样就要遍历两次，时间复杂度就大了。后来根据课上的提示，ID在数组中，然后调用一个循环开始遍历，相邻两两进行比较，如果不相同则消掉，在数组中的编号也随之一起改变，指导遍历完毕，就能够找到水王了。

代码实现：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     //首先假定用户的ID列表为一个数组
 7     int Id[30]={1,2,2,4,2,1,3,2,6,5,2,4,2,2,1,2,3,2,2,2,4,4,5,2,2,2,1,2,1,2};
 8     int ShuiW=Id[0];   //默认水王为第一个Id
 9     int count=1;
10     for(int i=1;i<30;i++)
11     {
12         if(Id[i]==ShuiW)   //判断与默认水王是否一样
13             count++;
14         else 
15             count--;
16         if(count==0)   //当count为0时候，说明这个水王不能占一半，则水王变为下一个。
17         {
18             ShuiW=Id[i];
19             count++;
20         }
21     }
22     if(count)   //当count为0时候，没有水王。
23         cout <<"水王Id:"<<ShuiW<<endl;
24     else
25         cout <<"没有水王"<<endl;
26     return 0;
27 }

运行截图：