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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    //Boyer-Moore 投票算法,如果一个元素出现次数 > n/2，那么它与其他所有元素“一对一抵消”后，剩下的一定是它自己。
    //从头开始遍历，第一个值默认为num，counter=1，往后遍历时，如果存在当前值与num相等，则counter++，否则，counter--
    //可以理解为这数组里面，一个数如果遇到相等的则出现次数+1，否则，出现次数-1，这样到最后超过一半次数的那个数出现次数一定是大于0的。
    //当counter重新为0时，说明前面出现了数组值等于num的数目和不等于num的数目相等，相当于此时否定了这个num
   //要给num赋给新的数，直到最后，num一定是数组中等于num的数目大于不等于num的数目的那个值。
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        if(numbers.size()==0)
        {
            return -1;
        }
        int num=0;
        int counter=0;//计数器
        for(int i=0;i<numbers.size();i++)
        {
            if(counter==0)//
            {
                num=numbers[i];
            }
            if(num==numbers[i])
            counter++;
            else
            counter--;
        }
        return num;
    }
};