首页 > 编程学习 > 【LeetCode】多数元素 II [M](摩尔投票)

【LeetCode】多数元素 II [M](摩尔投票)

发布时间:2022/12/3 14:45:59

229. 多数元素 II - 力扣(LeetCode)

一、题目

给定一个大小为 的整数数组,找出其中所有出现超过 ⌊ 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<Integer> majorityElement(int[] nums) {
        HashMap<Integer, Integer> cntMap = new HashMap<>();
        int n = nums.length;
        List<Integer> ans = new ArrayList<Integer>();
        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<Map.Entry<Integer, Integer>> iterator = cntMap.entrySet().iterator();
                    while (iterator.hasNext()) {
                        Map.Entry<Integer, Integer> 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次,超过了就加入到ans
        for (Map.Entry<Integer, Integer> 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的,就将这个候选值从表中删除。
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号