229. 多数元素 II - 力扣（LeetCode）

一、题目

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

示例 1：

输入：nums = [3,2,3]
输出：[3]

示例 2：​​​​​​​

输入：nums = [1]
输出：[1]

示例 3：​​​​​​​

输入：nums = [1,2]
输出：[1,2]

提示：

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

二、代码

class Solution {public List majorityElement(int[] nums) {HashMap cntMap = new HashMap<>();int n = nums.length;List ans = new ArrayList();int k = 3;for (int i = 0; i < n; i++) {// 候选表中存在nums[i]if (cntMap.containsKey(nums[i])) {// 直接将该值的血量++int value = cntMap.get(nums[i]);cntMap.put(nums[i], value + 1);// 候选表中不存在nums[i]} else {// 当前Map表还没有满，就将nums[i]加入到Map候选表中，作为候选值if (cntMap.size() < k - 1) {cntMap.put(nums[i], 1);// 当前Map表已经满了，就将表中所有候选值的血量减1，然后如果剪到0的从Map中移除} else {// 使用迭代器边遍历，边移除才不会报错Iterator> iterator = cntMap.entrySet().iterator();while (iterator.hasNext()) {Map.Entry entry = iterator.next();int key = entry.getKey();int value = entry.getValue();if (--value == 0) {iterator.remove();} else {cntMap.put(key, value);}}}}}// 如果没有候选值，就说明这个表里面没有次品为n/k的数if (cntMap.size() == 0) {return ans;}// 找到候选值，去遍历数组来确定他们的真实词频，然后判断是否超过了n/k次，超过了就加入到ansfor (Map.Entry entry : cntMap.entrySet()) {int key = entry.getKey();int cnt = 0;for (int i = 0; i < n; i++) {if (nums[i] == key) {cnt++;}}if (cnt > n / k) {ans.add(key);}}   return ans;}
}

三、解题思路 

上面的代码写的是通用解，可以找到数组中所有词频大于n/k的值。

通过遍历数组，维护候选值和对应的血量，只要最后又剩下的候选值，就说明有可能存在词频大于n/k的数，然后在数组中遍历一下候选值，统计他们的真实词频，看是否大于n/k，是的话就加入到ans中。

维护规则：

• 遍历数组时碰到了候选值，就将这个候选值对应的血量++。
• 如果此时有表还没有满，并且遍历到的数不是候选值，就将这个数加入到表中作为一个候选值。
• 如果此时候选值表已经满了，遍历到的数又不是候选值，那么就将表中所有的候选值血量--，如果出现血量为0的，就将这个候选值从表中删除。