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

【题目】

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

【分析】

采用阵地攻守的思想：
第一个数字作为第一个士兵，守阵地；count = 1；
遇到相同元素，count++;
遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一般即可。

【代码】

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    if(numbers.empty())
            return 0;
        int result = numbers[0];
        int times = 1;
        for(int i=1; i<numbers.size(); ++i){
            if(times == 0){
                times = 1;
                result = numbers[i];
            }
            else if(result == numbers[i])
                ++times;
            else
                --times;
        }

        if(!check_more_than_half(numbers, result))
            result = 0;
        return result;
    }
private:
    bool check_more_than_half(vector<int>& numbers, int result){
    int cnt = 0;
        for(int i=0; i<numbers.size(); ++i){
           if(numbers[i] == result)
                ++cnt;
        }

        return cnt*2>numbers.size() ? true : false;
    }

};