找水王

一、题目

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

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

二、设计思想

一开始的想法是遍历一遍记录每个id出现的次数，但这样牺牲了空间太大。后来老师提示用两两消除法，于是就用这个方法。先设两个值WaterWang，num，分别记录水王id和当前判定为水王id重复的次数（开始默认为1）。一开始默认第一个为水王id，两两相同时保留并num+1；两两不同时num-1，并舍弃该值，并且当num降至0时，要将将下一个数暂定为水王，num还原为1，继续循环。

三、代码实现

 1 //找水王
 2 //王文奇 20132980 2016/5/16
 3 #include<iostream>
 4 using namespace std;
 5 int main()
 6 {
 7     int size = 0;
 8     int num = 1; //当前判定为水王ID重复的次数
 9     int WaterWang;
10     cout << "请输入ID个数：";  
11     cin >> size;
12     int *ID = new int[size];
13 
14     cout << "请输入ID(请保证水王ID个数大于数量的一半)：" << endl;
15     for (int i = 0; i < size; i++)
16     {
17         cin >> *(ID + i);
18     }
19 
20     WaterWang = ID[0]; //一开始默认为数组中的第一个数为水王
21     for (int i = 1; i<size; i++)
22     {
23         if (WaterWang != ID[i])     //两两不同时舍弃
24         {
25             num = num - 1;   //水王次数减一
26             if (num <= 0)    //当水王次数降至0以下时
27             {
28                 WaterWang = ID[i + 1];   //暂定下一个数为新水王
29                 num = 1;  //水王次数重新赋为一
30                 i++;   //跳过ID[i]的判断
31             }
32         }
33         else                     //两两相同时暂定为水王
34         {
35             WaterWang = ID[i];
36             num = num + 1;   //水王次数加一
37         }
38     }    
39     cout << "水王id为：" << WaterWang << endl;    
40     delete[] ID;
41 
42     return 0;
43 }

四、实现截图

五、个人总结

一开始的想法很简单，但就是想不到更好的方法，在老师的提点下才完善了这个算法。总之，遇到问题还应多有些新想法。