题解 | #数组中出现次数超过一半的数字#

class Solution {
public:
    //投票算法（候选人算法）
    //算法思想如下：如果每次从数组中挑选出来两个数，如果这两个数不相同则直接去除这两个数
    ///如果相同则这种数的个数加2
    //那么最后这个数组中剩下的一定就是出现次数最多的数（前提是有一种数出现次数超过了一半）
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    //初始时假设numbers[0]就是候选人即出现次数最多的数
        int candidate=-1,count=0;//候选人是谁，现在有多少个票数
        int n=numbers.size();
        for(int i=0;i<n;i++){
            if(count==0){//当没有候选人时，挑选当前数成为候选人
                candidate=numbers[i];
                count=1;
            }
            else if(numbers[i]==candidate)//当前数和候选人相同时,票数加1
                count++;
            else{//不同时票数减1
                count--;
            }
        }
        return candidate;
    }
};