2.3 寻找发帖"水王"

1,问题实质:寻找数组中出现的半数以上的数.

int MoreHalfNum(int data[], int n)
{
    int ret;
    int nTime = 0;
    for (int i = 0; i < n; ++i)
    {
        if (nTime == 0)
        {
            ret = data[i];
            ++nTime;
        }
        else
        {
            if (data[i] == ret)
                ++nTime;
            else
                --nTime;
        }
    }
    return ret;
}

2,拓展:有3个数,他们的出现次数都超过了总数的1/4.

void nMoreNum(int data[], int n, int& ret1, int& ret2, int& ret3)
{
    int nTime1 = 0;
    int nTime2 = 0;
    int nTime3 = 0;

    for (int i = 0; i < n; ++i)
    {
        if (nTime1 == 0)
        {
            ret1 = data[i];
            ++nTime1;
        }
        else if (nTime2 == 0)
        {
            ret2 = data[i];
            ++nTime2;
        }
        else if (nTime3 == 0)
        {
            ret3 = data[i];
            ++nTime3;
        }
        else
        {
            if (data[i] == ret1)
                ++nTime1;
            else if (data[i] == ret2)
                ++nTime2;
            else if (data[i] == ret3)
                ++nTime3;
            else //注意这里
            {
                --nTime1;
                --nTime2;
                --nTime3;
            }

        }
    }
}