求众数Ⅱ

一、要求

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

输入: [3,2,3]
输出: [3]

示例 2:

输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

二、思路

这道题算是众数Ⅰ的进阶，有关众数Ⅰ的解法，请参考我的另外一篇文章求众数。

数组元素中出现次数超过n/3的元素，最多是两个。因此我们设置变量a，b用来记录目标元素，用aTimes，bTimes记录对应元素出现的次数。

首先必须保证a和b不相同，然后遍历数组，遍历到的当前元素记为temp，如果temp=a，则aTimes++，如果temp=b，则bTimes++，如果都不想等，则aTimes--，bTimes--，任何时候计数器为0的元素，需要将此元素变更为当前元素。

那么一轮遍历结束后，产生了两个有可能的元素，需要统计他们在数组中出现的次数，比较完毕之后，加入list中并返回。

三、代码实现

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int a = 0;
        int b = 0;
        int aTimes = 0;
        int bTimes = 0;
        for (int temp : nums) {
            //当计数器为0时，需要变更a，但不能变更为与b相同的元素
            if ((aTimes == 0 && temp != b) || temp == a) {
                a = temp;
                aTimes++;
            } else if (bTimes == 0 || temp == b) {
                b = temp;
                bTimes++;
            } else {
                aTimes--;
                bTimes--;
            }
        }
        //统计两个元素出现的次数
        int size = nums.length / 3;
        aTimes = 0;
        bTimes = 0;
        for (int c : nums) {
            if (c == a) {
                aTimes++;
            } else if (c == b) {
                bTimes++;
            }
        }
        if (aTimes > size) {
            list.add(a);
        }
        if (bTimes > size) {
            list.add(b);
        }
        return list;
    }