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。诉说着自己怀才不遇，天道不公时，咱们早就一头扎根在自己的事业中，闷声发大财，搞自己的事业，这才是最正确的，而不是像一个臭平民一样，几十个人聚集在一起，把帽子脱下来，在地下踩上几脚，又有什么用呢