1. 首页
  2. LeetCode

每日一道 LeetCode (39):多数元素

每日一道 LeetCode (39):多数元素

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:每日一道 LeetCode (39):多数元素

题目来源:https://leetcode-cn.com/problems/majority-element/

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

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

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

解题方案一:哈希表

这道题我看到的我一个想法就是能把它放到一个 Map 里面,用当前元素做为 key ,然后用出现的频次做为 value 。

这样,只要在循环中,出现了 value 大于数组的一半,那么就可以直接返回了。

public int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    if (nums.length == 1) return nums[0];
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i])) {
            map.put(nums[i], map.get(nums[i]) + 1);
            // 如果当前大于一半直接返回
            if (map.get(nums[i]) > nums.length / 2) {
                return nums[i];
            }
        } else {
            map.put(nums[i], 1);
        }
    }

    return -1;
}

每日一道 LeetCode (39):多数元素

暴力方案简单是简单,问题是效率忒差了点。

解题方案二:排序

答案上的第二个方案相当的直接,直接对整个数组进行排序,然后取一半的位置,因为题目中讲众数是大于一半的,那么我们取一半的位置肯定不会错。

public int majorityElement_1(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

每日一道 LeetCode (39):多数元素

解题方案三:随机数

这个方案很有意思,直接取随机数,然后判断取到的这个随机数是不是众数,因为众数会大于一半,那么我们取随机数就有一半的几率直接取到我们想要的值。

这个方案的耗时基本靠脸,我也是醉了。

public int majorityElement_2(int[] nums) {
    int count = nums.length / 2;
    Random rand = new Random();
    while (true) {
        int index = rand.nextInt(nums.length);
        if (countOccurences(nums, nums[index]) > count) {
            return nums[index];
        }
    }

}

// 计算 num 出现的次数
private int countOccurences(int[] nums, int num) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == num) {
            count++;
        }
    }
    return count;
}

每日一道 LeetCode (39):多数元素

这个方案我提交了几次,最差耗时是 2ms ,最好是 1ms ,我估计多提交几次还可能能刷出来 0ms 。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code