遇到的問題都有解決的方案，希望我的博客可以為你提供一些幫助

圖片源自leetcode?

題目：169. 多數元素 - 力扣（LeetCode）

一、排序法

題目要求需要找到多數值（元素個數>n/2）并返回這個值。一般會想到先排個序，再取中間值；因為在有序數組中多數值（元素個數>n/2）的中間值必定是多數值。

代碼如下：

class Solution:def majorityElement(self, nums: List[int]) -> int:nums.sort()return nums[len(nums)//2]

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(),nums.end());return nums[nums.size()/2];}
};

復雜度分析?

時間復雜度：

使用的排序算法時間復雜度是

空間復雜度：

?在原數組上排序，無額外空間開銷

結果

二、哈希表法

一個比較常規的思路是：對于每一個元素我可以記錄它出現的次數，最后返回出現次數最多的元素就行。這樣問題就變成了如何在無序的數組中精確的識別出每一個元素，并且記錄他們出現的次數。哈希表天然適配，哈希表提供key-value鍵值映射，key可用于記錄數組中的元素，value可用于累計出現的次數。

class Solution:def majorityElement(self, nums: List[int]) -> int:ans={}for num in nums:ans [num]=ans.get(num,0)+1return max(ans,key=ans.get)

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int ,int> ans;int n=nums.size();for (auto num :nums){ans[num]++;if (ans[num]>n/2){return num;}}return -1;}
};

復雜度分析：

?時間復雜度：只需要遍歷一次數組

空間復雜度：最壞情況下需要與元素組等大的空間，但在本題目中明確指出了多數元素是存在的所以最多需要空間不大于 n/2

?三、摩爾投票法（Boyer-Moore Voting Algorithm）

1. 基本思想

摩爾投票法是一種用于?快速尋找數組中出現次數超過一定比例的元素?的算法。其核心思想是通過?“抵消”?策略，在遍歷數組時維護候選元素及其計數，最終找到可能的眾數。

• 經典問題：在數組中找出出現次數超過?n/2?的元素（即嚴格眾數）。

• 擴展問題：找出所有出現次數超過?n/k?的元素（如?k=3，找出出現次數超過?n/3?的元素）。

2. 算法步驟（以尋找嚴格眾數為例）

1. 初始化：
   設置候選元素?candidate?和計數器?count，初始值為?None?和?0。

2. 遍歷數組：
   對每個元素?num：

   • 如果?count == 0，設當前元素為候選（candidate = num）。

   • 如果?num == candidate，計數器加一（count += 1）。

   • 否則，計數器減一（count -= 1）。

3. 驗證結果：
   最終需再次遍歷數組，確認?candidate?的出現次數是否超過?n/2。

3. 示例分析

以數組?nums = [3, 2, 3]?為例，尋找嚴格眾數（出現次數 > 3/2 = 1.5，即至少出現 2 次）：

步驟	當前元素	candidate	count	操作
1	3	3	1	count=0 → 選為候選
2	2	3	0	不同 → count減1
3	3	3	1	count=0 → 重新選為候選

最后驗證?3?出現 2 次，滿足條件。

4. 擴展：尋找出現次數超過?n/k?的元素

若需找出所有出現次數超過?n/k?的元素（例如?k=3），需維護?k-1?個候選元素及其計數器。

步驟：

1. 初始化：
   維護?k-1?個候選和計數器，如?candidate1, count1?和?candidate2, count2（當?k=3?時）。

2. 遍歷數組：

   • 若當前元素與任一候選相同，對應計數器加一。

   • 若不同且某計數器為 0，替換候選并重置計數器為 1。

   • 否則，所有計數器減一。

3. 驗證候選：
   統計所有候選的實際出現次數，確認是否超過?n/k。

5. 對于本題目而言如何應用

思路：
多數元素出現次數大于數組長度一半，利用抵消思想，每次找到兩個不同元素就抵消掉，最后剩下的就是多數元素。遍歷數組，維護一個候選元素?candidate?和其出現次數?count?。遇到相同元素，count?加 1；遇到不同元素，count?減 1 ，若?count?為 0 ，更新?candidate?為當前元素并將?count?設為 1 。

class Solution:def majorityElement(self, nums: List[int]) -> int:candidate = Nonecount = 0for num in nums:if count == 0:candidate = numcount += 1 if num == candidate else -1# 驗證return candidate if nums.count(candidate) > len(nums) // 2 else -1

class Solution {
public:int majorityElement(vector<int>& nums) {int condidate =NULL;int count=0;for (auto num:nums){if (count==0){condidate=num;}count=count++?condidate==num:count--;}return condidate;}
};

尋找出現次數超過 n/3 的元素

def majorityElement_3(nums):candidate1, count1 = None, 0candidate2, count2 = None, 0for num in nums:if num == candidate1:count1 += 1elif num == candidate2:count2 += 1elif count1 == 0:candidate1, count1 = num, 1elif count2 == 0:candidate2, count2 = num, 1else:count1 -= 1count2 -= 1# 驗證候選res = []for c in [candidate1, candidate2]:if nums.count(c) > len(nums) // 3:res.append(c)return res

結果：

6. 復雜度分析

• 時間復雜度：O(n)
  僅需兩次遍歷數組（第一次找候選，第二次驗證）。本題中只需遍歷一次，不需要驗證（題干條件已給出一定有多數元素）。

• 空間復雜度：O(1)
  僅需常數空間存儲候選和計數器。

---

7. 與其他方法對比

方法	優點	缺點
摩爾投票法	O(1) 空間	需驗證結果
哈希統計	直觀，可統計所有元素	O(n) 空間，不適用于大數據流

---

摩爾投票法可以在線性時間和常數空間內高效解決多數元素問題，尤其適合處理大規模數據或內存受限的場景。