【小Y学算法】⚡️每日LeetCode打卡⚡️——45.多数元素

呆呆敲代码的小Y

发布于 2021-10-08 17:16:47

2780

发布于 2021-10-08 17:16:47

前言

算法题

每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
提示：本专栏解题编程语言一律使用 C# 和 Java 两种进行解题
要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧
今天是力扣算法题持续打卡第45天

原题样例：多数元素

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

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

示例 1：

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

示例 2：

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

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按非递减顺序排列
-1000 <= target <= 1000
仅存在一个有效答案

C#方法：投票法

众数总比非众数多因此最终能让票数count保持大于0的数就是众数。

注意:每当count变回0时就更换候选人，继续统计后续票数。

思路解析

代码：

public class Solution {
    public int MajorityElement(int[] nums) {       
       //投票法   
        int condidate = nums[0];
        int count = 1;
        for(int j = 1;j<nums.Length;j++)
        {   
            if(count == 0)
            {
                count = 1;
                condidate = nums[j];
                continue;
            }            
            if(nums[j] != condidate)
            {
                count--;
            }   
            else
            {
                count++;
            }                
        }
        return condidate;                  
    }
}

执行结果

通过
执行用时：108 ms，在所有 C# 提交中击败了76.44%的用户
内存消耗：29.8 MB，在所有 C# 提交中击败了27.49%的用户

Java 方法一：哈希表

思路解析

我们知道出现次数最多的元素大于⌊ 2/n⌋ 次，所以可以用哈希表来快速统计每个元素出现的次数。

我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组nums并将数组中的每个元素加入哈希映射中。在

这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

代码：

class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            } else {
                counts.put(num, counts.get(num) + 1);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }
}

执行结果

通过
执行用时：13 ms，在所有 Java  提交中击败了21.51%的用户
内存消耗：38.6 MB，在所有 Java 提交中击败了52.15%的用户

复杂度分析

时间复杂度：O( n )
空间复杂度：O( n )

Java 方法二：随机化

代码：

class Solution {
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    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;
    }

    public int majorityElement(int[] nums) {
        Random rand = new Random();

        int majorityCount = nums.length / 2;

        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }
}

执行结果

通过
执行用时：1 ms，在所有 Java  提交中击败了99.96%的用户
内存消耗：44.5 MB，在所有 Java 提交中击败了12.18%的用户

总结

今天是力扣算法题打卡的第四十五天！
文章采用 C#和 Java 两种编程语言进行解题
一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
那今天的算法题分享到此结束啦，明天再见！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-10-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

java

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

java

编程算法

登录后参与评论

0 条评论

热度