编程之美2.3 寻找发帖"水王"

题目：

传说，Tango有一大“水王”，他不但喜欢发帖，还会回复其他ID发的帖子，发帖数目超过帖子总数的一半，如果你有一个当前论坛上所有帖子的列表，其中帖子作者的ID也在表中，你能快速找到这个传说中的Tango水王吗?

算法思想：

如果每次删除两个不同的ID，在剩下的ID列表中，“水王”ID出现的次数仍然超过总数的一半，可以不断重复这个过程，把ID列表总数减小。

int passHalfNum(int *list,int n)
{
    if(list==NULL || n<=0)
    {
        cout<<"the input is wrong"<<endl;
    }
    int ret,num=0;
    for(int i=0;i<n;i++)
    {
        if(num==0)
        {
            ret=list[i]; num++; continue;
        }
        if (list[i]==ret)
        {
            num++;
        }else
        {
            num--;
        }
    }
    return ret;
}

随着Tango的发展，管理员发现，“超级水王”没有了。统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？

void solve(int *list,int n,int &one,int &two,int &three)
{
    if(list==NULL || n<=3)
    {
        cout<<"the input is wrong"<<endl; exit(0);
    }
    int availableValue=-1;
    one=two=three=availableValue;
    int num1=0,num2=0,num3=0;
    for(int i=0;i<n;i++)
    {
        if(list[i]==one)
        {
            num1++; continue;
        }
        if(list[i]==two)
        {
            num2++; continue;
        }
        if (list[i]==three)
        {
            num3++; continue;
        }
        if(num1==0)
        {
            num1++; one=list[i]; continue;
        }
        if(num2==0)
        {
            num2++; two=list[i]; continue;
        }
        if(num3==0)
        {
            num3++; three=list[i]; continue;
        }
        num1--;
        num2--;
        num3--;
    }
}

编程之美2.3 寻找发帖"水王"

原文：http://blog.csdn.net/richard_rufeng/article/details/19303421