多数元素

🟢 Easy · 🏷️ 数组、哈希表 · LeetCode#169

📖 题目

数组里出现次数超过 ⌊n/2⌋ 的元素叫多数元素，保证一定存在，找出它。

输入	输出	说明
[3,2,3]	3
[2,2,1,1,1,2,2]	2	出现4次 > ⌊7/2⌋=3

🆕 新知识

max(iterable, key=func) 里的 key 传的是函数本身（拿去当比较依据的工具），不是调用结果：

count = Counter(nums)
max(count, key=count.get)   # 遍历 count 的 key，按 count.get(key) 的大小比较，返回最大的那个 key

💡 思路

朴素解法：用 Counter 数出现次数，取最大的那个——直接、好写。

更省空间的解法（摩尔投票法）：多数元素出现次数超过一半，可以想象成"每来一个不同的元素就跟当前候选人对消一个"，对消到 0 就换候选人。因为多数元素数量上占绝对优势，撑到最后活下来的候选人一定是它——这个结论依赖"多数元素确实存在"这个前提，题目已经保证了，如果没保证还得再遍历一次验证。

nums = [2,2,1,1,1,2,2]
candidate=2,count=1 → count=2（同类）→ 遇到1，对消 count=1
count=0（再对消一次）→ 换人 candidate=1,count=1 → 对消 count=0
换人 candidate=2,count=1 → 遍历结束，candidate=2 就是答案

💻 代码

摩尔投票法（推荐，O(1) 空间）

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = 0
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

时间复杂度 O(n)，空间复杂度 O(1)。

哈希表计数（更直观，面试可以先写这个保底）

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = Counter(nums)
        return max(count, key=count.get)

时间复杂度 O(n)，空间复杂度 O(n)。