当前位置: 首页 > news >正文

LeetCode做题记录(第二天)169. 多数元素

题目:169. 多数元素

标签:数组 哈希表 分治 计数 排序
题目信息:
在这里插入图片描述

思路一:

在题目中出现了计数,那我们就可以直接考虑考虑使用哈希表
unordered_map
即遍历的时候记录每个数的出现次数,当出现次数大于n/2时,则返回这个数,这样就可以完成题目了。

代码实现:

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int>mp;//元素:出现次数int n=nums.size();int falg = n/2;for(int i=0;i<n;i++){mp[nums[i]]++;if(mp[nums[i]]>falg){return nums[i];}}return 0;}
};

时间复杂度分析:
一层for,O(n)

思路二:

这个思路是我在评论区看到的,很巧妙。
他把这个比作是帮派大乱斗,由于有个帮派的人数始终大于n/2,那么在大乱斗一换一的情况下,最后活着的人一定是这个帮派。

代码实现:

class Solution {
public:int majorityElement(vector<int>& nums) {int n=nums.size();int falg = n/2;int ans = nums[0];int cnt = 1;for(int i=1;i<n;i++){if(nums[i]==ans){cnt++;}else{cnt--;if(cnt==0){ans = nums[i];cnt = 1;}}}return ans;}
};

时间复杂度分析:
一层for,也是O(n)
但是由于没有开新的空间,所以空间复杂度很小,O(1)

总结:

出现计数相关的就考虑哈希表

ps:哇,做题写题解真是花时间但又不得不做。还是得好好规划时间。主要还是抖音太费时间,加油加油,加油沉淀。
补充下我最近在一个群里看到群友发出来的话,让我很有触动:

还没开始干,还没学习java基础,就开始拉群问自己有没有可能学得会,还没开始投简历之前就在群里抱怨社会不公平。你就算知道世界不公平,那有什么用呢?也就只是和一堆负能量的人聚集在一起,不光得不到什么情绪价值,每天还会被别人影响,干扰你的判断能力。两个教训总结,跟着别人的节奏一起吐槽。殊不知人家吃穿不愁。而你,浪费你的大把时间。我要是及早醒悟,早点远离这些神经病,内鬼,当别人还在抱怨social的不公,聚集起来批判social。诉说着自己怀才不遇,天道不公时,咱们早就一头扎根在自己的事业中,闷声发大财,搞自己的事业,这才是最正确的,而不是像一个臭平民一样,几十个人聚集在一起,把帽子脱下来,在地下踩上几脚,又有什么用呢

http://www.lryc.cn/news/403351.html

相关文章:

  • Adobe XD中文设置指南:专业设计师的现场解答
  • CentOS 7 安装Jenkins2.346.1(war方式安装)
  • 使用Java -jar运行就jar包时报异常:org.yaml.snakeyaml.error.YAMLException异常
  • golang实现的ab测试http代理工具
  • Maven学习——Maven的下载、安装与配置(详细攻略!)
  • C#知识|账号管理系统-修改账号按钮功能的实现
  • bug等级和优先级
  • 记录|C# winform布局学习
  • C/C++ json库
  • C++案例四:简易记事本程序
  • 【VUE学习】day03-过滤器filter
  • 技术成神之路:设计模式(八)责任链模式
  • 【Zynq UltraScale+ RFSoC】~~~
  • STM32之八:IIC通信协议
  • mysql的数据往hive进行上报时怎么保证数据的准确性和一致性
  • 问题:4、商业保险与政策性保险的主要不同之处是:经营主体不同、经营目标不同、承保机制不同。 #学习方法#其他#学习方法
  • Getx学习笔记之中间件鉴权
  • 介绍 Elasticsearch 中的 Learning to Tank - 学习排名
  • 2024年计算机软考中级【硬件工程师】面试题目汇总(附答案)
  • ThinkPad改安装Windows7系统的操作步骤
  • 微软Edge浏览器全解析教程
  • 【过题记录】7.20
  • Linux系统学习日记——vim操作手册
  • 【深度学习图片】图片清洗,只留下图像中只有一张人脸的,而且人脸是全的
  • 如何在 PostgreSQL 中处理海量数据的存储和检索?
  • 【中项】系统集成项目管理工程师-第2章 信息技术发展-2.2新一代信息技术及应用-2.2.1物联网与2.2.2云计算
  • Redis集群的主从复制原理-全量复制和增量复制-哨兵机制
  • 23年阿里淘天笔试题 | 卡码网模拟
  • 【SpringBoot】单元测试之测试Service方法
  • 剪辑师和小白都能用的AI解说神器,一键把短剧变解说视频-手把手教程-2024