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

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

思路一：

在題目中出現(xiàn)了計數(shù)，那我們就可以直接考慮考慮使用哈希表
unordered_map
即遍歷的時候記錄每個數(shù)的出現(xiàn)次數(shù)，當出現(xiàn)次數(shù)大于n/2時，則返回這個數(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;}
};

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

思路二：

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

代碼實現(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;}
};

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

總結(jié)：

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

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

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