摩尔投票法——一个计数器如何“一票定音“找出众数？

多数元素是最朴素的数组题，却藏着算法思维的分水岭：哈希表 O(n) 空间人人都行，但"只用两个变量、单遍扫完"的 1981 年投票算法，才能一路推广到 >n/3、>n/k 和流式场景。本文讲透直觉、严格证明、三语言实现与 229 的双候选推广。

引子：多数元素——最朴素的问题，藏着算法思维的分水岭

给你一个数组，找出出现次数超过一半的元素。LeetCode 169，一道 Easy。大多数人第一反应是哈希表：统计每个元素的次数，扫完再找超过 n/2 的那个。

哈希表没错，O(n) 时间很漂亮。但空间是 O(n)——如果面试官紧接着说"能不能 O(1) 空间？"，很多人才意识到：这道 Easy 题真正的考点是**"能不能用常数空间做出来"**。

答案是一个 1981 年就提出的算法——摩尔投票法（Boyer-Moore Majority Vote）[1]。它只用两个变量，单次遍历，就找到多数元素。还能一路推广到"超过 n/3 的元素"（229），甚至"超过 n/k"，天然适配数据流。

一、多数元素：为什么空间才是分水岭

1.1 题目

169. 多数元素：给定大小为 n 的数组 nums，返回其中的多数元素（出现次数 > ⌊n/2⌋）。题目保证多数元素存在[2]。

1.2 直觉解法

• 哈希表：统计次数，O(n) 时间、O(n) 空间——正确但"不优雅"

• 排序：排序后取 nums[n/2]，O(n log n) 时间、O(1) 空间——空间达标但时间退化

1.3 为什么"常数空间"是分水岭

数据量百万级时，O(n) 空间在内存上吃不消。更重要的是，"单遍 + 常数状态"意味着可以流式处理——数据不用全部载入内存。这个性质把摩尔投票与"只能离线"的哈希/排序区分开。

二、摩尔投票的直觉：投票与抵消

2.1 一个候选 + 一个计数器

维护 candidate（当前候选）和 count（票数），遍历时执行三条规则[1][3]：

for x in nums:
① 若 count == 0：candidate = x，count = 1 # 没人当候选，你上
② 否则若 x == candidate：count += 1 # 支持者投一票
③ 否则：count -= 1 # 反对者抵消一票

2.2 为什么众数"抵消不完"

把数组想象成选举：candidate 是当前领先者，count 是领先票数，遇到不同元素就抵消一票。

为什么多数元素一定留到最后？ 因为多数元素出现 > n/2 次，其他元素加起来 < n/2 次。即便所有非多数票全部用来抵消多数票，也是 多数票 > 非多数票——抵消不完，剩下的净领先票必属多数元素[4]。

三、正确性证明：不变量是灵魂

不变量：任意时刻，count 等于"候选者的票数中，尚未被其他元素抵消掉的部分"。

归纳证明：

• 初始：candidate 空、count=0，不变量成立

• ①换候选（count==0）：旧候选已被完全抵消，提当前元素为候选、count=1，即"1 张未抵消票"，成立

• ②支持（x==candidate）：新来一张支持票，未抵消票数 +1，成立

• ③反对（x≠candidate）：来一张反对票，抵消 1 张未抵消票，成立

结论：若多数元素 m 出现 > n/2 次，其票数大于其余票数之和，无论反对票如何分配，m 的票永远不可能被全部抵消——结束时 candidate 必为 m[4]。

一句话：这不是"碰巧猜对"，而是每个元素都真实参与了投票与抵消，多数者凭数量优势必然胜出。

四、LeetCode 169 实战：三语言实现

4.1 C++

class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = 0, count = 0;
for (int x : nums) {
if (count == 0) { candidate = x; count = 1; }
else if (x == candidate) count++;
else count–;
}
return candidate;
}
};

4.2 Python

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

4.3 Java

class Solution {
public int majorityElement(int[] nums) {
int candidate = 0, count = 0;
for (int x : nums) {
if (count == 0) { candidate = x; count = 1; }
else if (x == candidate) count++;
else count–;
}
return candidate;
}
}

4.4 一题多解对比

解法

时间

空间

流式

备注

注意：169 保证多数元素存在，第一遍投票结果无需验证[2]——这点在 229 里会反转。

五、LeetCode 229 推广：>n/3 的"双候选博弈"

5.1 题目与"最多两个"

229. 众数 II：返回所有出现次数 > ⌊n/3⌋ 的元素。

关键事实：出现次数 > n/3 的元素最多只有 2 个——若有 3 个，3 × (>n/3) > n，矛盾[5]。

所以 229 本质：用"两个候选 + 两个计数器"跑一遍投票，找最多两个候选，再第二遍扫描验证是否真 > n/3。

5.2 双候选算法流程

维护 (c1,c2) 与 (cnt1,cnt2)
第一遍（抵消提名）：
for x in nums:
if x == c1: cnt1++
elif x == c2: cnt2++
elif cnt1 == 0: c1 = x; cnt1 = 1
elif cnt2 == 0: c2 = x; cnt2 = 1
else: cnt1–; cnt2– # 三个阵营互相抵消
第二遍（验票）：
统计 c1、c2 真实出现次数，保留 > n/3 的

5.3 第二遍验证：新手最容易漏的坑

• 169：题目保证存在多数元素 → 第一遍候选一定是答案

• 229：可能没有 > n/3 的元素 → 第一遍候选只是"提名"，可能"名不副实"

例：[1, 2, 3]，各出现一次，第一遍会提名两个候选（如 2、3），但没有任何元素 > n/3=1。不二次验证就会把 2、3 都错当答案[5]。

"先提名、后验票"——这是 229 教给我们最重要的一课。

5.4 一般化到 >n/k

推广到"k-1 个候选 + k-1 个计数器"，可解"所有出现次数 > n/k 的元素"[6]：

规律：出现次数 > n/k 的元素，最多 k-1 个。
第一遍：维护 k-1 组候选，互相抵消
第二遍：统计真实次数，保留 > n/k 的候选

复杂度：O(n) 时间、O(k) 空间（k 通常为小常数）。

六、流式场景与我的观点

6.1 数据流众数

"单遍 + 常数状态"让摩尔投票在数据流场景大放异彩：实时日志统计、在线投票、传感器数据流——数据边到边处理，无需存储全部历史[6]。

6.2 与 DSA-26 位运算的呼应

上一期讲位运算的常数空间技巧（异或去重、lowbit）。摩尔投票是又一个"反直觉但优雅"的常数空间算法——算法思维的分水岭，往往就在于"敢不敢丢弃多余状态"。

6.3 我的三条心得

心得一：Easy 题的隐藏考点是"空间意识"。 169 用哈希表 5 分钟能过，但"O(1) 空间"的追问才是面试真正在测的——你有没有"压缩状态"的直觉。

心得二："先提名、后验票"是通用心智模型。 从 229 到现实中"草拟方案再复核"，两阶段思维无处不在。

心得三：证明比直觉可靠。 摩尔投票"感觉对"，但写出不变量、做归纳证明，才算真正掌握——这也是 DSA 系列强调的"以教促学"。

参考资料

• [1] Boyer & Moore 1981《MJRTY – A Fast Majority Vote Algorithm》（一级）

• [2] LeetCode 169 官方题解（一级）

• [3] doocs/leetcode 题解库：Moore Voting（二级）

• [4] CodeBricks《Majority Element: Boyer-Moore Voting Algorithm》（三级）

• [5] LeetCode 229 官方题解（一级）

• [6] 力扣讨论区《摩尔投票，解决所有 1/2、1/3、1/4 的众数问题》（二级）

• [7] AlgoMonster：169/229 解法拆解（二级）