面试题 17.10. 主要元素

class Solution {
    public int majorityElement(int[] nums) {
        /**
         摩尔投票法 模板
         */
        int candidate=-1,vote=0;
        for(int num:nums){
            if(vote==0){
                //还没有初始化
                candidate=num;
            }
            if(candidate==num){
                //一样
                vote++;
            }else{
                //不一样
                vote--;
            }
        }
        int count=0;//记录出现的candidate次数
        for(int i:nums){
            if(i==candidate){
                count++;
            }
        }
        if(count>nums.length/2){
            return candidate;
        }else{
            return -1;//没找到
        }
    }
}