? 牛客的刷題之路不停歇 ???

? 不積跬步無以至千里，不積小流無以成江海

? The harder you work,the luckier you will be??

---

題目及示例

題目鏈接

描述

? ? 給一個長度為 n 的數組，數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。

? ? 例如輸入一個長度為9的數組[1,2,3,2,2,2,5,4,2]。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。

數據范圍：n≤50000n≤50000，數組中元素的值?0≤val≤100000≤val≤10000

要求：空間復雜度：O(1)O(1)，時間復雜度?O(n)O(n)

輸入描述

? ? 保證數組輸入非空，且保證有解

樣例

---

題目解讀

? ? 查找數組中元素數量超過整個數組元素數量一半的元素

? ? 可通過記錄每個元素出現的次數來實現相應問題的查找

---

方法一（取巧的解決方法）：

思路：

? ??已知，數組非空，且一定有解，那就一定有一個元素的數量超過一半，我們只需要通過對數組進行排序，然后取中間值即可

思路說明：
如數組 { 1，5，7，2，2，2，2，2}排序后為{1，2，2，2，2，2，5，7}

再如數組{1，3，5，5，5，5，4}排序后為{1，3，4，5，5，5，5}

因為該元素的數量超過整個數組數量的一半，所以其不管大小，排序后必定經過數組中心

?核心代碼：

int MoreThanHalfNum_Solution(vector<int>& numbers) {sort(numbers.begin(),numbers.end());return numbers[numbers.size()/2];}

---

方法二（哈希表）：

思路：

? ? 通過哈希表記錄每個元素的出現個數，當達到目標時返回答案即可

• 先構建一個map容器用于哈希表
• 通過 for 循環對每個元素進行試探
• 通過對map容器的應用進行對其進行++操作
• 當容器中有元素的數量到達目標時，直接返回答案

核心代碼：

int MoreThanHalfNum_Solution(vector<int>& numbers) {unordered_map<int,int> hx;for(int i=0;i<numbers.size();i++){hx[numbers[i]]++;if(hx[numbers[i]] > numbers.size()/2){                               return numbers[i];}                         }                                                                         return 0;}

---

希望能給你提供一下參考思路

??ヽ(°▽°)ノ?