靈感來源?
- 保持更新，努力學習
- python腳本學習
多數元素
解題思路
這道題是要找出數組中出現次數超過一半的元素。有幾種不同的方法可以解決這個問題：
-
哈希表統計法：遍歷數組，用哈希表統計每個元素的出現次數，然后找出次數超過一半的元素。時間復雜度和空間復雜度都是 O (n)。
-
排序法：如果將數組排序，那么下標為 n/2 的元素（n 為數組長度）一定是眾數。時間復雜度取決于排序算法，通常是 O (n log n)，空間復雜度 O (1)（如果是原地排序）。
-
摩爾投票法：這是一種非常巧妙的算法，時間復雜度 O (n)，空間復雜度 O (1)。它的核心思想是：在每一輪投票過程中，從數組中找出一對不同的元素并刪除，直到數組為空或只有一種元素。由于眾數的出現次數超過一半，因此最終剩下的元素一定是眾數。
class Solution:def majorityElement(self, nums: List[int]) -> int:count = 0candidate = Nonefor num in nums:if count == 0:candidate = numcount += (1 if num == candidate else -1)return candidate
逐行解釋
class Solution:def majorityElement(self, nums: List[int]) -> int:# 初始化計數器為0count = 0# 初始化候選眾數為Nonecandidate = None# 遍歷數組中的每個元素for num in nums:# 當計數器為0時，意味著之前的候選眾數已被抵消完# 此時將當前元素設為新的候選眾數if count == 0:candidate = num# 如果當前元素等于候選眾數，計數器加1# 否則計數器減1（相當于一對不同元素相互抵消）count += (1 if num == candidate else -1)# 由于眾數出現次數超過一半，最終候選眾數即為所求眾數return candidate
)
