LeetCode229 求众数II 摩尔投票算法

本文主要是介绍LeetCode229 求众数II 摩尔投票算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述：

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

示例：

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

题解：

摩尔投票算法：
摩尔投票算法的核心思想是对拼抵消，首先我们考虑最基本的摩尔投票问题，比如找出一组数字序列中出现次数大于总数1/2的数字，易知若该元素存储，则只会存储一个这样的数。假设这个数是nums[0]，初始其票数为1，

那么对摩尔投票进行扩展，求大于n/3的所有元素，易知该元素最多有两个，因此我们可以初始化两个element，按和上面一样的流程，最后将出现次数大于n/3的element加入到结果集中即可。

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int element1 = 0;
        int element2 = 0;
        int vote1 = 0;
        int vote2 = 0;

        for (int num : nums) {
            if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
                vote1++;
            } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
                vote2++;
            } else if (vote1 == 0) { // 选择第一个元素
                element1 = num;
                vote1++;
            } else if (vote2 == 0) { // 选择第二个元素
                element2 = num;
                vote2++;
            } else { //如果三个元素均不相同，则相互抵消1次
                vote1--;
                vote2--;
            }
        }

        int cnt1 = 0;
        int cnt2 = 0;
        for (int num : nums) {
            if (vote1 > 0 && num == element1) {
                cnt1++;
            }
            if (vote2 > 0 && num == element2) {
                cnt2++;
            }
        }
        // 检测元素出现的次数是否满足要求
        List<Integer> ans = new ArrayList<>();
        if (vote1 > 0 && cnt1 > nums.length / 3) {
            ans.add(element1);
        }
        if (vote2 > 0 && cnt2 > nums.length / 3) {
            ans.add(element2);
        }

        return ans;
    }
}

LeetCode题解及动画演示

这篇关于LeetCode229 求众数II 摩尔投票算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！