哪个网站做系统好,wordpress 支持 手机版,游戏网站平台大全游戏网,虚拟主机空间域名题目#xff1a;169. 多数元素
标签#xff1a;数组 哈希表 分治 计数 排序 题目信息#xff1a;
思路一#xff1a;
在题目中出现了计数#xff0c;那我们就可以直接考虑考虑使用哈希表 unordered_map 即遍历的时候记录每个数的出现次数#xff0c;当出现次数大于n/…题目169. 多数元素
标签数组 哈希表 分治 计数 排序 题目信息
思路一
在题目中出现了计数那我们就可以直接考虑考虑使用哈希表 unordered_map 即遍历的时候记录每个数的出现次数当出现次数大于n/2时则返回这个数这样就可以完成题目了。
代码实现
class Solution {
public:int majorityElement(vectorint nums) {unordered_mapint,intmp;//元素:出现次数int nnums.size();int falg n/2;for(int i0;in;i){mp[nums[i]];if(mp[nums[i]]falg){return nums[i];}}return 0;}
};时间复杂度分析 一层forO(n)
思路二
这个思路是我在评论区看到的很巧妙。 他把这个比作是帮派大乱斗由于有个帮派的人数始终大于n/2那么在大乱斗一换一的情况下最后活着的人一定是这个帮派。
代码实现
class Solution {
public:int majorityElement(vectorint nums) {int nnums.size();int falg n/2;int ans nums[0];int cnt 1;for(int i1;in;i){if(nums[i]ans){cnt;}else{cnt--;if(cnt0){ans nums[i];cnt 1;}}}return ans;}
};时间复杂度分析 一层for也是O(n) 但是由于没有开新的空间所以空间复杂度很小O(1)
总结
出现计数相关的就考虑哈希表
ps哇做题写题解真是花时间但又不得不做。还是得好好规划时间。主要还是抖音太费时间加油加油加油沉淀。 补充下我最近在一个群里看到群友发出来的话让我很有触动 还没开始干还没学习java基础就开始拉群问自己有没有可能学得会还没开始投简历之前就在群里抱怨社会不公平。你就算知道世界不公平那有什么用呢也就只是和一堆负能量的人聚集在一起不光得不到什么情绪价值每天还会被别人影响干扰你的判断能力。两个教训总结跟着别人的节奏一起吐槽。殊不知人家吃穿不愁。而你浪费你的大把时间。我要是及早醒悟早点远离这些神经病内鬼当别人还在抱怨social的不公聚集起来批判social。诉说着自己怀才不遇天道不公时咱们早就一头扎根在自己的事业中闷声发大财搞自己的事业这才是最正确的而不是像一个臭平民一样几十个人聚集在一起把帽子脱下来在地下踩上几脚又有什么用呢
