课堂作业——找水军

题目：

　　随着论坛的发展，管理员发现水王没有了，但是统计结果表明，有三个发帖很多的ID。据统计他们的发帖数量超过了1/4，你能从发帖列表中快速找到他们吗？

思路：

　　编程之美的扩展了这个问题，在求解找出一个“水王”的基础上进行补充分析，之前遍历数组的时候只用保存两个值：一个是数组中的ID，一个是它对应出现的次数。而这次需要找出3个ID（即输出3个结果），就需要另开辟新的数组来分别保存。首先保存前3个ID，每当遍历下一个ID的时候，先要判断下一个和当前保存的这3个ID是否有相同的，若有相同的则此ID对应的次数加1；若不同则次数减1。再判断如果有ID次数为零，就用下一个ID把它替换，并把次数设为1。与之前不同的是，可能会出现次数都不为0的情况，这时就将所有的次数都减1。

源代码：

 1 #include<iostream.h>
 2 #define N 16
 3 class Type
 4 {
 5     public:
 6     Type()
 7     {
 8         count=0;
 9         id=-1;
10     }
11     int count;
12     int id;
13 };
14 int main()
15 {
16         int ID[N]={7,10,7,4,5,5,10,7,7,7,10,10,5,5,10,4};    
17         Type candidate1;
18         Type candidate2;
19         Type candidate3;
20     int i;
21     for(i=0;i<N;i++)
22     {
23         if(ID[i]==candidate1.id)
24                 {
25             candidate1.count++;
26                 }
27         else if(ID[i]==candidate2.id)
28                 {
29             candidate2.count++;
30                 }
31         else if(ID[i]==candidate3.id)
32                 {
33             candidate3.count++;
34                 }
35         else if(candidate1.count==0)
36         {
37             candidate1.id=ID[i];
38             candidate1.count++;
39         }
40         else if(candidate2.count==0)
41         {
42             candidate2.id=ID[i];
43             candidate2.count++;
44         }
45         else if(candidate3.count==0)
46         {
47             candidate3.id=ID[i];
48             candidate3.count++;
49         }
50         else
51         {
52             candidate1.count--;
53             candidate2.count--;
54             candidate3.count--;
55         }
56     }
57     cout<<candidate1.id<<endl;
58     cout<<candidate2.id<<endl;
59     cout<<candidate3.id<<endl;
60     return 0;
61 }
62

View Code

运行结果：

总结：

　　因为还要考虑时间复杂度，所以就按照上次的代码进行修改，每次把当前保存的三个ID分别展开（if...else），与下一个ID进行比较，在对其对应的次数操作加、减。

　　在论坛上看见有用类和结构体来定义新数组的，这样就不会每次比较时还要遍历新的数组，缩短了时间复杂度。很久没涉及了，现在看到又回忆起来了一些，温故而知新，也知道了什么时候可以用什么结构和方法。