寻找小水王

一、题目

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

目超过了帖子数目的一半。如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？但是随着论坛的发展，管理员

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

二.算法思想：

因为三个“小水王”发帖数是大于总帖数的1/4，所以到最后总会有使得记录次数的值>0。

用含三个元素的water_ID[3]分别记录找到的小水王ID值，用含三个元素的数组count[3]作为计数器。

每次选取一个ID与water_ID比较，若有相同则计数器加一，若与三个water_ID都不相同，则三个计数器均减1。

若count减至为0，则这个ID出现的次数不符合要求，重新给该water_ID赋值。

三、代码

#include<iostream>
#define N 10000
using namespace std;

void water_max(int ID[],int num)    //寻找该帖子列表中三个“小水王”的ID值即water_ID[0]、water_ID[1]、water_ID[2]，即出现次数大于帖子数1/4的ID值
{
    int count[3]={0,0,0};    //用于寻找三个小水王的计数
    int water_ID[3]={0,0,0};    //将小水王的ID值water_ID[]先初始化为0
    for(int i=0;i<num;i++)    //寻找小水王    
    {
        if(count[0]==0&&water_ID[1]!=ID[i]&&water_ID[2]!=ID[i])    //当count[0]的值为0,ID[i]不等于其他两个water_ID时赋给water_ID[0],count[0]的值加一
        {
            water_ID[0]=ID[i];
            count[0]++;
        }
        else if(count[1]==0&&water_ID[0]!=ID[i]&&water_ID[2]!=ID[i])    //当count[1]的值为0,ID[i]不等于其他两个water_ID时赋给water_ID[1],count[1]的值加一
        {
            water_ID[1]=ID[i];
            count[1]++;
        }
        else if(count[2]==0&&water_ID[0]!=ID[i]&&water_ID[1]!=ID[i])    //当count[2]的值为0,ID[i]不等于其他两个water_ID时赋给water_ID[2],count[2]的值加一
        {
            water_ID[2]=ID[i];
            count[2]++;
        }
        else if(water_ID[0]==ID[i])    //当count[0]不等于0,ID[i]的值等于water_ID[0],count[0]加一
        {
            count[0]++;
        }
        else if(water_ID[1]==ID[i])    //当count[0]不等于0,ID[i]的值等于water_ID[1],count[1]加一
        {
            count[1]++;
        }
        else if(water_ID[2]==ID[i])    //当count[0]不等于0,ID[i]的值等于water_ID[2],count[2]加一
        {
            count[2]++;
        }
        else if(water_ID[0]!=ID[i]&&water_ID[1]!=ID[i]&&water_ID[2]!=ID[i])    //当ID[i]的值不等于任一water_ID[],三个计数器count均减一
        {
            count[0]--;
            count[1]--;
            count[2]--;
        }
    }
    cout<<"该论坛中小水王的ID为:"<<water_ID[0]<<" "<<water_ID[1]<<" "<<water_ID[2]<<endl;
}

int main()
{
    int num;
    int ID[N];

    cout<<"请输入帖子总数:"<<endl;
    cin>>num;

    cout<<"请依次输入帖子列表中作者ID:"<<endl;
    for(int i=0;i<num;i++)
    {
        cin>>ID[i];
    }

    water_max(ID,num);    //主函数中调用water_max寻找并输出三个小水王的ID值

    return 0;
}

四、运行结果截图