我们知道，水王问题：有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; }
