多数元素（Majority Element）是算法面试中的高频题目：给定一个大小为 n 的数组，找出其中出现次数大于 n/2 的元素。最直观的做法是借助哈希表统计每个元素的出现次数，但这样需要额外的空间。摩尔投票法（Boyer-Moore Voting Algorithm）则以O(n)时间复杂度和O(1)空间复杂度完美解决了这个问题，思路巧妙且代码极短，非常值得深入理解。
一、常规解法回顾：从暴力到排序
在讲摩尔投票法之前，先看看几种容易想到的解法，理解它们的瓶颈，才能体会摩尔投票法的精妙之处。
第一种是暴力统计法。使用字典遍历数组，把每个元素作为键，出现次数作为值，统计完成后再遍历字典找到次数超过 n/2 的元素。这种方法时间复杂度为O(n)，空间复杂度也是O(n)，思路简单但空间开销不小：
def majority_element_hash(nums):
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
for num, c in count.items():
if c > len(nums) // 2:
return num
return -1第二种是排序法。如果某个元素出现次数超过一半，那么将数组排序后，下标为 n//2 的位置必然是这个元素，无论它偏向数组的哪一端。例如数组 [2,2,1,1,1,2,2] 排序后为 [1,1,1,2,2,2,2]，中间位置的元素就是 2。这种方法代码只有一行，但排序的时间复杂度是 O(n log n)，且多数语言中排序还需要额外空间，效率不如线性算法。
第三种是随机取值法。随机挑选一个元素，验证它是否为多数元素。由于多数元素占比超过一半，每次随机命中的概率大于 50%，期望尝试次数接近 2 次，理论上期望时间复杂度是O(n)。但它依赖随机性，最坏情况不保证线性时间，面试中一般只作为思路补充。
二、摩尔投票法核心原理：两两抵消的战斗
摩尔投票法的核心思想可以用一场投票来形象理解。想象一个会场里坐满了支持不同候选人的人，每个人都坚持自己的立场不动摇。规则是：每当两个人立场不同，他们就同时离场，互相抵消；立场相同的人则聚在一起等待下一轮对抗。
关键结论在于：如果某个候选人的支持者超过总人数的一半，那么即使其他所有人联合起来与其对抗，抵消殆尽之后，留在场内的最后一批人仍然属于这个候选人。换句话说，多数元素与其他所有元素两两抵消后，剩余的必然还是多数元素，因为它的数量严格大于总数的一半，其他元素加起来也不够把它完全抵消掉。
算法的实现只需要两个变量：候选者 candidate 和计数器 count。遍历数组时，如果 count 为 0，就把当前元素设为新的候选者；如果当前元素与候选者相同，count 加一；否则 count 减一，表示一次抵消。完整代码如下：
def majority_element(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num # 无人可用，当前元素成为新候选者
count = 1
elif num == candidate:
count += 1 # 同阵营，票数增加
else:
count -= 1 # 异阵营，互相抵消一票
return candidate用一个具体例子走一遍流程。以数组 [3,2,3,3,2,3] 为例：开始时 candidate 为空，遇到 3 后 candidate=3，count=1；遇到 2 发生抵消，count=0；再遇到 3，candidate 更新为 3，count=1；遇到 3，count=2；遇到 2，count=1；遇到 3，count=2。遍历结束时 candidate 为 3，正是多数元素。
需要注意的一点是，摩尔投票法找到的候选者只有在题目保证多数元素存在时才是正确答案。如果无法保证存在（比如数组 [1,2,3] 根本没有多数元素），最后得到的 candidate 只是抵消后剩下的元素，并不代表它出现次数过半。此时需要再遍历一次数组做校验：
def majority_element_verified(nums):
# 第一阶段：投票选出候选者
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count = 1
elif num == candidate:
count += 1
else:
count -= 1
# 第二阶段：校验候选者是否真的过半
if nums.count(candidate) > len(nums) // 2:
return candidate
return None # 多数元素不存在加上校验后，整体时间复杂度依然是O(n)，只是多了一趟遍历，空间复杂度仍然保持O(1)，这是工程上更稳妥的写法。
三、各方案对比与变体问题延伸
把前面提到的所有解法放在一起对比，可以更清楚地看到摩尔投票法的优势：
| 解法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 哈希统计 | O(n) | O(n) | 思路直接，空间开销大 |
| 排序取中位 | O(n log n) | 视排序实现而定 | 代码最短，但非线性能耗 |
| 随机取值 | 期望O(n) | O(1) | 最坏情况不稳定 |
| 摩尔投票法 | O(n) | O(1) | 最优解，推荐掌握 |
摩尔投票法还能推广到求出现次数超过 n/3 的元素这类变体问题。由于这样的元素最多只有两个，可以同时维护两对候选者和计数器，按照同样的抵消逻辑处理：与候选者相同则加票，与两个候选者都不同则三票互相抵消。最后同样需要二次遍历来校验两个候选者的真实出现次数，剔除不满足条件的元素。
def majority_element_third(nums):
# 求出现次数超过 n/3 的所有元素，最多两个
c1, c2, cnt1, cnt2 = None, None, 0, 0
for num in nums:
if c1 == num:
cnt1 += 1
elif c2 == num:
cnt2 += 1
elif cnt1 == 0:
c1, cnt1 = num, 1
elif cnt2 == 0:
c2, cnt2 = num, 1
else:
cnt1 -= 1 # 三方混战，三票一起抵消
cnt2 -= 1
# 校验阶段
result = []
for c in (c1, c2):
if c is not None and nums.count(c) > len(nums) // 3:
result.append(c)
return result总结一下，遇到寻找多数元素的问题时，优先想到摩尔投票法。理解它的关键在于抓住抵消的本质：多数元素的数量优势保证了它在完全抵消后依然存活。写代码时注意两个细节，一是 count 为 0 时要切换候选者，二是不能保证多数元素存在时务必做二次校验，掌握这两点，这类问题就能稳定拿下了。