題目：169. 多數(shù)元素

標(biāo)簽：數(shù)組 哈希表 分治 計(jì)數(shù) 排序
題目信息：

思路一：

在題目中出現(xiàn)了計(jì)數(shù)，那我們就可以直接考慮考慮使用哈希表
unordered_map
即遍歷的時(shí)候記錄每個(gè)數(shù)的出現(xiàn)次數(shù)，當(dāng)出現(xiàn)次數(shù)大于n/2時(shí)，則返回這個(gè)數(shù)，這樣就可以完成題目了。

代碼實(shí)現(xiàn)：

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int>mp;//元素:出現(xiàn)次數(shù)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;}
};

時(shí)間復(fù)雜度分析：
一層for，O(n)

思路二：

這個(gè)思路是我在評(píng)論區(qū)看到的，很巧妙。
他把這個(gè)比作是幫派大亂斗，由于有個(gè)幫派的人數(shù)始終大于n/2，那么在大亂斗一換一的情況下，最后活著的人一定是這個(gè)幫派。

代碼實(shí)現(xiàn)：

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;}
};

時(shí)間復(fù)雜度分析：
一層for，也是O(n)
但是由于沒有開新的空間，所以空間復(fù)雜度很小，O(1)

總結(jié)：

出現(xiàn)計(jì)數(shù)相關(guān)的就考慮哈希表

ps：哇，做題寫題解真是花時(shí)間但又不得不做。還是得好好規(guī)劃時(shí)間。主要還是抖音太費(fèi)時(shí)間，加油加油，加油沉淀。
補(bǔ)充下我最近在一個(gè)群里看到群友發(fā)出來的話，讓我很有觸動(dòng)：

還沒開始干，還沒學(xué)習(xí)java基礎(chǔ)，就開始拉群?jiǎn)栕约河袥]有可能學(xué)得會(huì)，還沒開始投簡(jiǎn)歷之前就在群里抱怨社會(huì)不公平。你就算知道世界不公平，那有什么用呢？也就只是和一堆負(fù)能量的人聚集在一起，不光得不到什么情緒價(jià)值，每天還會(huì)被別人影響，干擾你的判斷能力。兩個(gè)教訓(xùn)總結(jié)，跟著別人的節(jié)奏一起吐槽。殊不知人家吃穿不愁。而你，浪費(fèi)你的大把時(shí)間。我要是及早醒悟，早點(diǎn)遠(yuǎn)離這些神經(jīng)病，內(nèi)鬼，當(dāng)別人還在抱怨social的不公，聚集起來批判social。訴說著自己懷才不遇，天道不公時(shí)，咱們?cè)缇鸵活^扎根在自己的事業(yè)中，悶聲發(fā)大財(cái)，搞自己的事業(yè)，這才是最正確的，而不是像一個(gè)臭平民一樣，幾十個(gè)人聚集在一起，把帽子脫下來，在地下踩上幾腳，又有什么用呢