加强版水王：找出出现次数刚好是一半的数字

我们知道，水王问题：有N个数，其中有一个数出现超过一半，要求在线性时间求出这个数。那么，我的问题是，加强版水王：有N个数，其中有一个数刚好出现一半次数，要求在线性时间内求出这个数。

因为，很明显，如果是刚好出现一半的话，如此例： 0，1，2，1 ：

方案一：

根据上面的例子，最后我们可能会输出不是符合条件的数字，那么仔细分析的话，占一半的数字，只能在两个变量中出现：candidate和arr[n-1]。如果arr[n-1]不是占一半的数据key，那么candidate最后保持着key，另一种情况，就是arr[n-1]为key。我们遍历到最后，再遍历一趟判断一下是否arr[n-1]占据一半即可。

改进：

我们再遍历的过程中，让每一个数据与arr[n-1]比较，统计和arr[n-1]相同的数据，那么到最后就不用再遍历了，代码如下：

int MoreThanHalf(int a[], int N)
{
    int sum1 = 0;//最后一个元素的个数
    int sum2 = 0;
    int candidate;
    int i;
    for(i=0;i<N-1;i++)//扫描前N-1个元素
    {
        if(a == a[N-1])//判断当前元素与最后一个是否相等
        sum1++;
        if(sum2 == 0)
        {
             candidate = a;
             sum2++;
        }
        else
        {
             if(a == candidate)
                 sum2++;
             else
                 sum2--;
        }
     }  

     if((sum1+1) == N/2)
         return a[N-1];
     else
         return candidate;
}