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

示例 1：

输入：[3,2,3]
输出：[3]
示例 2：

输入：nums = [1]
输出：[1]
示例 3：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.*;

class Solution {

    private void reduce(Map<Integer, Integer> candidateMap) {
        Iterator<Map.Entry<Integer, Integer>> iterator = candidateMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> entry = iterator.next();
            if (entry.getValue() == 1) {
                iterator.remove();
            } else {
                entry.setValue(entry.getValue() - 1);
            }
        }
    }

    public List<Integer> majorityElement(int[] nums) {
        int k = 3;
        int limit = k - 1;
        Map<Integer, Integer> candidateMap = new HashMap<>(limit);
        for (int num : nums) {
            if (candidateMap.containsKey(num)) {
                candidateMap.put(num, candidateMap.get(num) + 1);
            } else {
                if (candidateMap.size() == limit) {
                    reduce(candidateMap);
                } else {
                    candidateMap.put(num, 1);
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        Map<Integer, Integer> cntMap = new HashMap<>(limit);
        for (int num : nums) {
            if (candidateMap.containsKey(num)) {
                int cnt = cntMap.getOrDefault(num, 0) + 1;
                if (cnt == (nums.length / 3 + 1)) {
                    ans.add(num);
                }
                cntMap.put(num, cnt);
            }
        }
        return ans;
    }
}