求众数——摩尔投票

摩尔投票算法

摩尔投票法适用于求解“数组中出现次数大于n/2,n/3,...的元素”的问题。它的思想是对拼消耗，从第一选手开始闯关，遇到“非我同类”就“同归于尽”，相反遇到“同类”就相伴而行，最后剩下的选手即为所求的众数。

不过需要注意的是，并非最后得到的结果即为所求，当前数组并不是一定就存在符合条件的众数(但如果存在的话则它必定是摩尔投票得到的那个结果)，因此最后还需要一个验证的过程。

169.多数元素(求出现次数大于⌊ n/2 ⌋的元素)

如果当前元素与候选者相同则归队，否则对拼消耗。

    public int majorityElement(int[] nums) {
        //已经确定存在多数元素，因此不再需要验证过程
        //if(nums==null||nums.length==0) return -1;
        int major=nums[0],cnt=0;
        for(int num:nums){
            if(cnt==0){
                major=num;
            }
            if(num==major) cnt++;
            else cnt--;
        }
        // cnt=0;
        // for(int num:nums){
        //     if(num==major) cnt++;
        // }
        // return cnt>nums.length/2?major:-1;
        return major;
    }

229.求众数 II(求出现次数大于⌊ n/3 ⌋的元素)

出现次数大于⌊ n/3 ⌋的元素最多有2个，因此需要两个计数器。当前元素如果等于候选者1则与与候选者1归队在一起，如果等于候选者2则与与候选者2归队在一起，如果与两个候选者都不相等，则与两个候选者均对拼消耗一次。需要注意的是两个候选者值必须不等。

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res=new ArrayList<>();
        if(nums==null||nums.length==0) return res;
        int major1=nums[0],major2=nums[0],cnt1=0,cnt2=0;
        for(int num:nums){
            //即便一开始num==major1==major2，最后major1和major2也是必不相等的。
            if(num==major1) cnt1++;
            else if(num==major2) cnt2++;
            else if(cnt1==0) {
                major1=num;
                cnt1++;
            }
            else if(cnt2==0) {
                major2=num;
                cnt2++;
            }
            else{
                cnt1--;
                cnt2--;
            }
        }
        cnt1=0;
        cnt2=0;
        for(int num:nums){
            if(num==major1) cnt1++;
            if(num==major2) cnt2++;
        }
        if(cnt1>nums.length/3) res.add(major1);
        if(cnt2>nums.length/3&&major1!=major2) res.add(major2);
        return res;
    }

扩展(求出现次数大于⌊ n/k ⌋的元素)

需要k-1个计数器。当前元素如果等于候选者i则与与候选者i归队在一起，否则与k-1个候选者均对拼消耗一次。