当前位置:首页 » 《随便一记》 » 正文

【小Y学算法】⚡️每日LeetCode打卡⚡️——45.多数元素_努力前行,总会成为自己心中的那道光

7 人参与  2022年02月22日 15:07  分类 : 《随便一记》  评论

点击全文阅读


        • 📢前言
    • 🌲原题样例:多数元素
      • 🌻C#方法:投票法
      • 🌻Java 方法一:哈希表
      • 🌻Java 方法二:随机化
    • 💬总结
        • 🚀往期优质文章分享

请添加图片描述


📢前言

🚀 算法题 🚀
  • 🌲 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程😜
  • 🌲 提示:本专栏解题 编程语言一律使用 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 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦,明天再见!
    请添加图片描述

🚀往期优质文章分享

  • ❤️Unity零基础到入门 | 游戏引擎 Unity 从0到1的 系统学习 路线【全面总结-建议收藏】!
  • 🧡花一天时间做一个高质量飞机大战游戏,过万字Unity完整教程!漂亮学妹看了直呼666!
  • 💛回忆童年和小伙伴一起玩过的经典游戏【炸弹人小游戏】制作过程+解析
  • 💚通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难
  • 🤍爆肝整整一个周末写一款类似 皇室战争 的 即时战斗类 游戏Demo!两万多字游戏制作过程+解析!
  • 💙一款类似“恐龙快打”的 横版街机格斗游戏 该如何制作?| 一起来学习 顺便送源码【码文不易,建议收藏学习】
  • 💜【超实用技巧】| 提高写文的质量 和 速率必学技能: Typora 图床配置 详细说明


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/35177.html

元素  算法  方法  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 此去经年人未还霍沉洲沈青禾后续结局霍沉洲
  • 山海不相逢内容精选(温逸尘沈衿)_山海不相逢内容精选(温逸尘沈衿)
  • (番外)+(全书)霍沉洲沈青禾此去经年人未还(霍沉洲沈青禾)_(霍沉洲沈青禾此去经年人未还)列表_笔趣阁(霍沉洲沈青禾)
  • (番外)+(全书)霍沉洲沈青禾(此去经年人未还霍沉洲沈青禾)完结_(霍沉洲沈青禾)列表_笔趣阁(此去经年人未还霍沉洲沈青禾)
  • 「重回八零,拒绝替嫁冲喜」章节彩蛋限时释出‌_卫东玉兰苏夏人气小说未删减节选
  • 重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费
  • 傅雅宁的神女老婆,却在背地承欢作乐顾尘傅雅宁全书在线
  • 全文神女老婆,却在背地承欢作乐全局(顾尘傅雅宁)列表_全文神女老婆,却在背地承欢作乐全局
  • (番外)+(全书)此去经年人未还全书+番外+后续免费下载_(沈青禾霍沉洲)此去经年人未还全书+番外+后续列表_笔趣阁(沈青禾霍沉洲)
  • 完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续列表_完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续(林梦婉)
  • 妻子辱我爸受贿自杀,我掏出一等军功章节选推荐_[陈素云辰朋友]小说精彩章节分享
  • 全书浏览苔藓爬满旧日诺言新上(顾砚廷慕晚夏)_苔藓爬满旧日诺言新上(顾砚廷慕晚夏)全书结局

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1