T229、求众数

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

解

摩尔投票的升级版本。首先可以明确的一点是，这样的元素可能有0个、1个、或者2个，再没有别的情况了.
然后，求众数I 里的 Boyer-Moore 算法思路在这里依然可用，但需要些改动：
1) 满足条件的元素最多有两个，那么需要两组变量. count, major变成了count1, major1; count2, major2;
2) 选出的两个元素，需要验证它们的出现次数是否真的满足条件.

 public List<Integer> majorityElement(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        if(nums.length < 1) return ret;
        int count1 = 0, count2 = 0;
        int major1 = nums[0], major2 = nums[0];
        
        for(int num : nums) {
            if(num == major1)
                count1++;
            else if(num == major2)
                count2++;
            else if(count1 == 0) {
                count1 = 1;
                major1 = num;
            }
            else if(count2 == 0) {
                count2 = 1;
                major2 = num;
            }
            else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for(int num : nums) {
            if(num == major1)
                count1++;
            else if(num == major2)
                count2++;
        }
        if(count1 > nums.length/3)
            ret.add(major1);
        if(major1 != major2 && count2 > nums.length/3)
            ret.add(major2);
        return ret;
    }