多数元素

问题拆解

多数元素是出现次数 严格大于 ⌊n/2⌋ 的元素，题目保证它一定存在。

最直接的想法是用哈希表统计每个元素出现多少次，再挑出次数过半的那个。这样思路清晰，但要额外花 O(n) 的空间。进阶要求把空间压到 O(1)，就得利用“过半”这个很强的条件，而不只是数数。

多数元素比其他所有元素加起来还多，如果让不同的元素两两抵消，最后剩下的必然是它。

哈希计数（作为对照）

def majorityElement(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
        if count[x] > len(nums) // 2:
            return x

这版本一眼就对，适合先确认题意。它的问题只在空间：最坏情况下要为几乎所有不同元素各记一笔。

摩尔投票

维护一个候选人 candidate 和一张票数 count。遍历时，票数为 0 就把当前元素立为新候选人；之后遇到相同元素票数加一，遇到不同元素票数减一——相当于一张反对票抵消一张支持票。

def majorityElement(nums):
    count = 0
    candidate = None
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

为什么最后剩下的一定是多数元素？把每个非多数元素看成消耗掉一张多数元素的票。多数元素的票数超过一半，其余所有元素加起来也不够把它的票全部抵消，所以无论顺序如何打乱，它的净票数始终为正，最终稳稳占据 candidate。

因为题目保证多数元素存在，这里不需要第二遍验证；如果不保证，还得再扫一遍确认候选人真的过半。

复杂度

指标	复杂度	原因
时间	O(n)	一次遍历完成抵消
空间	O(1)	只保存候选人和票数

可以迁移的模式

• 存在一个“数量占绝对优势”的元素；
• 允许用抵消、配对来消去噪声，而不是精确计数；
• 目标是把空间从 O(n) 压到常数。

摩尔投票还能推广到“出现次数超过 ⌊n/3⌋”，那时维护两个候选人即可。