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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        int res=numbers[0];
        int count =1;
        for(int i=1;i<numbers.size();i++){
            if(count == 0){
                res=numbers[i];
                count++;
            }
            else if(numbers[i]==res) count++;
            else{
                count--;
            }
        }
        return res;
    }
};

摩尔投票法：现有 n 个人投票选出一人上台，其中有一个党派人数超过 n/2,O(n)算法找出这个党派，从编号 1 开始上台当擂主，维护一个擂主的票数，遍历数组，同党派则票数加 1，不同党派则票数减 1，票数为 0 则下一个人当擂主，最后留在台上的必然是人数超过 n/2 的党派，可理解成此党派有绝对的人数优势，就算其他人全部反对也一定能上台。