52.Majority Element-众数

题目描述：

解析：摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
        //摩尔投票法
        int majorValue=0;
        int count=0;
        for(int num:nums){
            if(count==0){ 
            majorValue=num;
            count+=1;
            }else if(num==majorValue){
                count+=1;
            }else{
                count-=1;
            }
        }
        return majorValue;
    }
}

变题：如果是要找出出现次数大于【n/3】的元素
同样使用摩尔投票法，改进版

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        //摩尔投票法的改进版
        int value1=0,value2=0,count1=0,count2=0;
        ArrayList<Integer> res = new ArrayList<>();
        for (int num : nums) {
            if(value1==num){
                count1+=1;
            }else if(value2==num){
                count2+=1;
            }else if (count1==0){
                value1=num;
                count1+=1;
            }else if(count2==0){
                value2=num;
                count2+=1;
            }else {
                count1-=1;
                count2-=1;
            }
        }
        if (count1>0){
            count1=0;
            for (int num : nums) {
                if(num==value1) count1+=1;
            }
            if (count1>nums.length/3) res.add(value1);
        }
        if (count2>0){
            count2=0;
            for (int num : nums) {
                if(num==value2) count2+=1;
            }
            if (count2>nums.length/3) res.add(value2);
        }
        return res;
    }
}