【LeetCode】求众数 IIJava 题解

关注

发布于: 1 小时前

题目描述

给定一个大小为 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* n)的时间。当选票有序时，可以很容易编出 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)
坚持算法每日一题，加油！

发布于: 1 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/660a555d79280d841b36dd13a】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】求众数 IIJava 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论