题目描述

给定一个大小为 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路分析

• 今天的算法每日一题是求众数，题目定义的众数是超过 n/3 次数的为众数。第一，我们可以遍历一遍 nums ,求出每个 num 出现的次数，然后用 hashMap 记录。在遍历一次 hashMap, 就可以得出题目要求的众数。实现代码如下：
• 这个题目还有一种解决方案是采用摩尔投票法，我们可以了解一下。摩尔投票法(Boyer–Moore majority vote algorithm)出自论文，算法解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。常见的算法是扫描一遍选票，对每个候选人进行统计的选票进行统计。当候选人的数目固定时，这个常见算法的时间复杂度为：O(n)，当候选人的数目不定时，统计选票可能会执行较长时间，可能需运行O(n * 2)的时间。当选票有序时，可以很容易编出O(n)的程序，第一找到中位数，然后检查中位数的个数是否超过选票的一半。这篇论文针对无序且侯选人不定的情形，提出了摩尔投票算法。算法的比较次数最多是选票（记为n）的两倍，可以在O(n)时间内选出获票最多的，空间开销为O(1)。

通过代码

• 朴素解法

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > n / 3) {
                ans.add(entry.getKey());
            }
        }

        return ans; 
    }
}
复制代码

总结

• 朴素解法的时间复杂度是O(n), 空间复杂度是O(n)
• 坚持算法每日一题，加油！

作者：HQ数字卡
链接：
https://juejin.cn/post/7021689367303290893
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。