找水王

一、实验要求

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

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

二、设计思想

每次比较两个相邻的ID是否一样，如果不一样则删除。首先假设第一个ID是水王，然后和第二个比较，看看是否相同，如果不同则把第二个命名为水王，一次类推，如果相同，则time++。在剩下的ID中，水王依然过半，重复这个过程，就可以找到水王。

三、源代码

 1 #include "stdafx.h"
 2 
 3 #include "iostream"
 4 
 5 using namespace std;
 6 
 7  
 8 
 9 int main()
10 
11 {
12 
13     int a[10]={1,3,2,3,2,3,1,3,3};
14 
15     int result = a[0];
16 
17     int times = 1;
18 
19     for(int i = 1; i < 10; i++)
20 
21     {
22 
23         if(a[i] == result)
24 
25             times++;
26 
27         else
28 
29             times--;
30 
31         if(times == 0)
32 
33         {
34 
35             result = a[i];
36 
37             times = 1;
38 
39         }
40 
41     }
42 
43     cout<<"水王为："<<result<<endl;
44 
45     return 0;
46 
47 }

四、运行结果

五、心得体会

这个实验我刚刚看到的时候一点思路都没有，后来老师提供了一个思路，先排序，然后找到一半位置上的ID即为水王，但是由于那个时间复杂度太高，需要优化，但是实在没有思路，后来经过来时的提示，才明白该如何做。