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