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

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //可以用候选者投票过半机制解决即摩尔投票法
        int candidate = array[0];
        //计票，设定第一个候选者，已经有一票
        int count =1;
        for(int i = 1;i<array.length;i++){
            if(array[i] == candidate){
                count++;
            }else{
                count--;
                if(count == 0){
                    //说明当前候选者票数与之前都抵消了，重新计票
                    candidate = array[i];
                    count = 1;
                }
            }
        }
        return candidate;
        
    }
}

摩尔投票法，这题很有意思。因为要求超过一半，所以可以用这个方法。设定数组第一个为当前候选者，如果它的票数与其他候选者的票数都抵消掉了，就换掉这个候选者，并且把票数重新记为1，这点很重要。等全部遍历结束，还有票数不为0的，就是选定的候选者。