数组中出现次数超过一半的数字

由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。我们维护两个变量，num和count,其中num为保存的数字，count为保存的数字的统计。
由于这是一个必要非充分条件，因此需要验证一下。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int len = numbers.size();
        if(len==0) return 0;
        int num = numbers[0],count = 1;
        for(int i = 1;i<len;++i){
            if(numbers[i]==num) ++count;
            else --count;
            if(count==0){  //放心，这里的count是不可能＜0的
                num = numbers[i];
                count = 1;
            }
        }
        //验证
        count = 0;
        for(int i = 0;i<len;++i){
            if(numbers[i]==num)
                count++;
        }
        return count>(len/2)?num:0;
    }
};