【LeetCode】主要元素 Java 题解

关注

发布于: 2 小时前

题目描述

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。


示例 1：
输入：[1,2,5,9,5,9,5,5,5]输出：5来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-majority-element-lcci著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题目容易理解，首先可以采用 HashMap 记录元素出现的次数求解。
因为题目要求空间复杂度是 O(1), 参考题解，采用摩尔投票法。投票算法的基本思想是：在每一轮投票过程中，从数组中删除两个不同的元素，直到投票过程无法继续，此时数组为空或者数组中剩下的元素都相等。

代码

朴素解法

    public int majorityElement(int[] nums) {        int ans = -1;        int n = nums.length;        Map<Integer, Integer> map = new HashMap<>();        for (int num : nums) {            int cnt = map.getOrDefault(num, 0) + 1;            if (cnt > n / 2) {                ans = num;                break;            }            map.put(num, cnt);
        }
        return ans;    }

复制代码

摩尔投票法

public int majorityElement(int[] nums) {        int candidate = -1;        int cnt = 0;        for (int num : nums) {            if (cnt == 0) {                candidate = num;            }            if (num == candidate) {                cnt++;            } else {                cnt--;            }        }
        cnt = 0;        for (int num : nums) {            if (candidate == num) {                cnt++;            }        } 
        int ans = -1;        int n = nums.length;        if (cnt * 2 > n) {            ans = candidate;        }
        return ans;
    }

复制代码

总结

朴素解法的时间复杂度是 O(n), 空间复杂度是 O(n)
摩尔投票法解法的时间复杂度是 O(n), 空间复杂度是 O(1)
坚持每日一题，加油！

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

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

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】主要元素 Java 题解

题目描述

思路分析

代码

总结

HQ数字卡

评论