空间寻找多数元素的原理与实战)
摩尔投票法（Boyer-Moore majority vote algorithm）是我在刷数组类题目时见过的最精巧的 O(1) 空间解法之一。它的任务很具体：在线性时间内，只用常数级额外空间，找出数组中出现次数超过 n/2 的多数元素。整段核心代码不过十行左右，但背后的抵消逻辑、边界判断和证明思路，藏着一整套值得拆解的细节。这篇文章想把算法从原理到实现、从证明到扩展讲透，适合准备算法面试的人，也适合在实际数据处理中需要省内存的人。只要你有过被哈希表空间占用困扰的经历，这篇内容应该能给你一个足够顺手的替代方案。
1. 多数元素到底在找什么：定义先行
1.1 一个容易被忽略的前提
算法领域有个习惯说法："出现次数最多的元素就是多数元素"。这句话在多数情况下不算错，但在摩尔投票法的语境下必须抠字眼。多数元素的定义是出现次数严格大于 n/2 的元素，而不是"频次最高"。
举个例子，数组 [1, 2, 2, 3] 里频次最高的是 2，出现了 2 次，n=4，n/2=2，2 不大于 2，所以这个数组没有多数元素。如果你按"频次最高"的思路去做，很容易在无多数元素的用例上翻车。经典题目通常会补充一句：如果不存在多数元素，返回值不作要求。但如果你要做严格版本，就需要二次遍历验证，这正是后面要单独讲的一节。
很多刷题新手会在这一步栽跟头，因为他们把"多数"等同于"出镜率第一"。摩尔投票法的前提是"压倒性多数"，即超过一半，这两者有本质区别。理解这个定义，你才能理解为什么算法用抵消而不是计数。
1.2 一眼想到的方案和它们的问题
先列出最朴素的解法：
- 哈希表统计法：遍历数组统计每个元素出现次数，再找出超过 n/2 的键。时间 O(n)，空间 O(n)。
- 排序法：先排序，如果多数元素存在，排序后它一定占据 nums[n/2] 这个位置。时间 O(n log n)，空间取决于排序算法。
- 分治法：递归地把数组分成两半，在左右子数组中分别找多数候选，再合并。时间 O(n log n)，空间 O(log n)。
这三种方案在面试中都说得过去，但换一个场景就捉襟见肘了。假设数据是从某个数据源流式进入的，总量可能有上亿条，你不能把它全部装进内存再排序，更不能维护一个庞大的哈希表。这时候"边读边算、只用两个变量"的摩尔投票法就是最优解。要理解它为什么能做到 O(1) 空间，得先接受一个核心思想：我们不需要精确统计每个人的票数，只需要让不同元素的票互相抵消。
我把三种方法放在一起对比，大家感受下各自的使用场景：
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 哈希表计数 | O(n) | O(n) | 不限制空间，代码最直观 |
| 排序取中位 | O(n log n) | O(log n) | 数据量不大，可接受重排 |
| 摩尔投票 | O(n) | O(1) | 大数据量、内存受限、流式输入 |
三种方法各有场合。哈希表写起来最快，不容易出错，如果是业务代码里偶尔用一次，我没理由非要用摩尔投票。但如果你面对的数据规模大到哈希表内存顶不住，或者数据是一个一个流式到达的，那 O(1) 空间的方法就不可替代了。
2. 核心机制：候选人和计数器是怎么配合的
2.1 两条规则看懂全部逻辑
摩尔投票法的实现可以压缩成两句话：
- 维护一个候选元素 candidate 和它的票数 count，初始时 candidate 为空，count 为 0。
- 遍历数组，对每个元素 x：
- 若 count == 0，把 candidate 设为 x，count 设为 1；
- 否则，若 x 与 candidate 相同，count 加 1；
- 否则，count 减 1。
遍历结束后，candidate 就是可能的多数元素。
你看，整个算法没有任何复杂的记忆和回溯，就是这么一个"见同类 +1、见异类 -1、归零就换人"的状态机。我第一次跑这段逻辑时，内心是拒绝的：这也太简单了吧？凭什么这样就能找到多数元素？后来想明白了，简单不等于平凡，这个状态机里埋着一个非常强的数学前提——超过半数的人站在同一边。
2.2 手动模拟一组数据
纸上得来终觉浅，我拿一个具体数组走一遍。假设输入是：
[2, 2, 1, 1, 1, 2, 2]
n = 7，多数元素应该是 2，因为 2 出现了 4 次，大于 7/2。
开始遍历：
| 当前元素 | candidate | count | 操作说明 |
|---|---|---|---|
| 2 | 2 | 1 | count 为 0，直接选 2 作候选人 |
| 2 | 2 | 2 | 与候选相同，count +1 |
| 1 | 2 | 1 | 与候选不同，count -1 |
| 1 | 2 | 0 | 与候选不同，count -1，归零 |
| 1 | 1 | 1 | count 为 0，换候选人 1 |
| 2 | 1 | 0 | 与候选不同，count -1，归零 |
| 2 | 2 | 1 | count 为 0，换候选人 2 |
最后 candidate 是 2，正确。注意中间出现过一次改选：在第五个元素时 count 归零，候选人从 2 换成了 1。这个"换届"非常关键，它是整个算法看起来最反直觉的地方——为什么半路要换候选人？
答案在抵消逻辑里。我们盯住的不是"谁暂时领先"，而是"当前剩余的票是否还撑得住当前候选人"。一旦 count 归零，说明从某个局部来看，候选人和它的对手打了个平手，此时这一整段可以整体抛弃，从下一个元素开始重新计票。多数元素在整个数组中占有压倒性优势，无论从哪个切割点重新计票，它最终都会赢得最后一段的"局部战场"。
2.3 为什么要设计成抵消而不是计数
如果只是想找出现次数最多的元素，哈希表是天然的直觉方案，但"出现次数最多"和"出现次数超过一半"是两个不同的目标。后者有一个决定性特征：它多出来的票永远比所有对手的总和还多。正因为存在这种压倒性优势，我们才敢用"抵消"这种方案——一对一对地消灭元素，多数元素必然能在混战中存活下来。
想象一个有 n 个人参加的投票，超过半数的人投给了同一个人 A。如果我把支持 A 的票和支持其他人的票两两配对，每对中最多只能有一个 A 支持者，那么配对到最后，至少会剩下一张没有对手的 A 的票。摩尔投票法的 count，其实就相当于"目前还没有被配对掉的支持票数量"。这个思路后面证明部分还会用到。
这也是选型层面的关键判断：当你确定要解决的是"是否存在超过半数的元素"这个问题时，摩尔投票法在时间、空间、代码复杂度三个维度上都是最优解；但如果你要的是"每个元素出现多少次"，那就老老实实上哈希表。先弄清自己要回答什么问题，再选算法，这才是不被"炫技"带偏的核心。
3. 从伪代码到可运行实现：代码不长，坑不少
3.1 Python 实现与逐行拆解
先把标准实现贴出来：
def majority_element(nums): candidate = None count = 0 for x in nums: if count == 0: candidate = x count = 1 elif x == candidate: count += 1 else: count -= 1 return candidate就这么点东西。注意一个细节：很多文章写的逻辑是"先判断 x == candidate 再判断 count == 0"，两种写法都能跑，但判断顺序会影响一个极端情况——当 count 为 0 且 x 恰好等于前一个 candidate 时，先加票会把 count 从 0 变成 1，而先选候选人会把 count 置为 1，两种结果看似一样，其实语义不同。先选候选人再判断相等，代码更干净，也符合状态机的直觉。
3.2 状态变量与不变量的含义
- candidate：当前阶段最有希望成为多数元素的幸存者。
- count：当前幸存者比对手多出来的"净胜票数"。它只反映相对优势，不反映绝对出现次数。
有一个容易搞混的点：count 为 3 不代表 candidate 真的连续出现了 3 次，只代表在已经遍历过的这段区间里，去掉与它抵消掉的对手后，它还净剩 3 张票。这也就是为什么算法结束时不能直接信任 candidate，必须二次验证。
还有一点，如果数组里确实存在多数元素，最终 candidate 一定等于它；如果不存在多数元素，candidate 可能是个无意义的元素。这个"必要条件但不充分"的性质，是理解整个算法的钥匙。我建议你在写完之后多跑几个边界用例，光看代码很难形成手感。
3.3 边界场景逐一过
我整理了几个值得测试的用例：
| 输入 | 结果候选 | 实际多数元素 | 说明 |
|---|---|---|---|
| [] | None | 无 | 空数组，candidate 为 None，需自己防御 |
| [5] | 5 | 5 | 单元素天然满足 > n/2 |
| [1, 2, 3] | 取决于遍历顺序 | 无 | 第一遍后必须验证，否则会误报 |
| [1, 2, 2, 1] | 取决于遍历顺序 | 无 | 两个元素各出现 n/2 次，没有多数元素 |
第四种情况很有意思：1 和 2 各出现两次，n=4，没有任何元素严格大于 2。算法跑完后 candidate 取决于抵消过程中谁先归零，可能返回 1 也可能返回 2。这就是为什么任何严格版本的实现都必须接一个验证循环。
4. 为什么它是对的：不变量证明与直觉双重拆解
4.1 核心不变量：每次抵消后 count 的物理意义
要证明摩尔投票法正确，最干净的方式是维护一个不变量：在遍历完前 i 个元素之后，如果我们把已经遍历的部分中 candidate 的支持票与其他所有票两两配对，那么 pair 完之后剩下的未配对票数恰好是 count。
我再用前面 [2, 2, 1, 1, 1, 2, 2] 验证一下这个不变量。遍历前 5 个元素 [2, 2, 1, 1, 1] 后，candidate 从 2 换成了 1，count 为 1。这段区间里，2 出现 2 次，1 出现 3 次，把 2 的 2 张票和 1 的 2 张票配掉，还剩 1 张 1 的票，和 count=1 吻合。遍历前 6 个元素后，candidate 是 1，count 是 0，此时区间 [2, 2, 1, 1, 1, 2] 里 2 有 3 票、1 有 3 票，正好全部配平。不变量成立。
这个不变量不会因为"换届"而被破坏，因为换届的本质是：旧候选人的净胜票已经降为 0，说明之前的区间内部完成了全量配对，我们直接把这个区间从视野中丢弃即可，新候选人重新起算。丢弃掉的区间里，多数元素的支持票与反对票至少是一比一的，所以丢弃它们不会削弱多数元素的全局优势。
4.2 多数元素必然存活的论证
假设数组中真正存在多数元素 M，它出现了 m 次，且 m > n/2。我们来看整个遍历过程中，M 的支持票被抵消的情况。任何一次 count 减 1，代表当前元素与 candidate 不同，也就是说，某一张票在和一张非 M 的票或者另一张反对票配。即便我们在最不利的假设下——每次 M 的支持票都被拿来抵消非 M 票——M 的票总共也不会被抵消超过 n-m 次，因为整个过程最多只有 n-m 张非 M 票存在。
关键计算在这：m > n-m，这意味着 M 的票数严格大于所有对手票数的总和。无论对手怎么分配这些票，M 的票永远配不完。所以不管候选人怎么换，最终必将停留在 M 上。注意 count 在这个过程中可能起起伏伏，但 M 的净胜票不可能变成负数——一旦 count 归零，我们丢弃的是完全配平的区间，M 在里面最多损失一半的票，不会危及全局。
4.3 用"巷战"类比理解幸存者逻辑
我把这个算法讲给朋友听时，用过这样一个比喻。假设一个巷子里有两拨人，一拨是多数派，一拨是少数派，规则是一个多数派成员和一个少数派成员相遇就同归于尽。由于多数派人数严格超过半数，他们哪怕单挑对单挑，最后也一定会有人活下来。摩尔投票法就是不看全局、只看当前幸存者是谁的模拟巷战。
这个比喻能解释"为什么 count 归零要换人"：当 count 归零，说明当前这段巷战打成了平手，双方同归于尽，这段历史对结果没有影响，我们从下一格重新开始。谁能在每条小巷里留到最后，只取决于总数上的压制力。巷战类比还有一个额外的好处：它提醒你算法的结果只有一个候选人，而候选人是不是真的多数派，必须到"战后清点人数"这一步才能确认。
5. 二次遍历验证：多数算法翻车重灾区
5.1 没有多数派时会发生什么
回到这个问题：数组 [1, 2, 3] 用摩尔投票法跑出来，candidate 是 3。3 只出现了 1 次，显然不是多数元素。问题在于算法根本不保证一定返回多数元素，它只保证"如果多数元素存在，返回它"。有无多数元素两种情况，算法的行为完全不同，而仅凭第一遍遍历你无法区分。
所以在需要严格答案的场景，标准的完整写法是两遍扫描：
def majority_element(nums): candidate = None count = 0 for x in nums: if count == 0: candidate = x count = 1 elif x == candidate: count += 1 else: count -= 1 # 二次验证 total = 0 for x in nums: if x == candidate: total += 1 if total > len(nums) // 2: return candidate return None第二遍遍历的时间复杂度同样是 O(n)，所以总时间复杂度仍是 O(n)。如果你面对的数据流只能走一遍，那么摩尔投票法第一遍只能给出候选，最终确认需要额外手段，这一点在流式场景中要提前说清楚。我自己在做流式聚合时，通常会把候选元素连同它的净胜票一起丢到下游，再由下游在窗口结束时决定是否可信。
5.2 什么时候可以安全跳过验证
有几种情况可以省略二次验证。一是题目明确保证存在多数元素，这是某刷题平台上编号 169 题的标准版本，很多人的实现直接返回 candidate。二是你处理的数据源本身有业务约束，能确保多数元素必然存在，比如某个监控系统中，超过半数节点的状态一定是"正常"之类。
但在工程实践中，我建议即使题目没有要求，也把验证逻辑留着。原因很现实：刷题环境可以假设数据干净，真实数据不会。多一层验证的成本极低，却能把"返回错误结果"变成"返回 None 并报警"，这对线上问题排查是质的差别。你可以把验证循环实现成独立函数，只在大数据量的关键路径上再考虑内联优化。
6. 从 n/2 到 n/3：摩尔投票法的泛化
6.1 多数元素 II：找出出现超过 n/3 的元素
某刷题平台上有一道进阶题：给定数组，找出所有出现次数超过 n/3 的元素。每个数组最多只能有两个这样的元素，证明也很简单：如果三个元素都超过 n/3，总数就超过 n 了。
泛化版摩尔投票法维护两个候选人和两个计数器：
def majority_elements(nums): cand1 = cand2 = None cnt1 = cnt2 = 0 for x in nums: if x == cand1: cnt1 += 1 elif x == cand2: cnt2 += 1 elif cnt1 == 0: cand1 = x cnt1 = 1 elif cnt2 == 0: cand2 = x cnt2 = 1 else: cnt1 -= 1 cnt2 -= 1 # 统计并验证 res = [] for x in set([cand1, cand2]): if x is not None and nums.count(x) > len(nums) // 3: res.append(x) return res判断顺序有个讲究：先比对两个候选人，再处理空位，最后才做双降，否则会出现新元素把已有候选人顶掉但另一个候选人也失守的情况。双候选人的状态机比单候选人复杂不少，强烈建议在纸上模拟几组数据再上手改代码。我当年改这个版本时，就因为把"先判空位"放在了"先比对候选"前面，在 [1, 2, 1, 2, 3] 这样的数据上跑出了错误结果，排查了好一会儿才发现是分支顺序的问题。
6.2 通用模板：超过 n/k 的候选人有 k-1 个
再往下推一步，如果题目改成"找所有出现次数超过 n/k 的元素"，答案的候选数量最多是 k-1 个。通用实现就是维护 k-1 对 (candidate, count)，遍历时依次比对，命中则加票，有空位则占用，落空则全部减一。时间和空间分别是 O(n) 和 O(k)。当然 k 一般不大会，否则算法的空间优势就稀释了。
这类泛化题在面试里出现频率不低，但核心思想并没变：利用"超过阈值的元素必然在抵消中存活"这个不变量。先掌握 n/2 版本，再理解 n/3 版本，最后能口头推导通用版本，基本就能应付大多数提问了。实际上，n/k 版本在工程里更常见，因为它能表达"超过一定占比的关键信号"这类语义。
6.3 流式数据与内存受限场景的实际价值
除了刷题，这个算法在真实场景里最大的价值是它不需要存数据。比如某个传感器持续上报状态码，你想要知道在最近一段时间内是否有某种状态码占据了绝对多数，摩尔投票法配合一个窗口计数器就能在线完成。哈希表会把所有状态码都记下来，内存随状态数增长；投票法只关心两个变量，即使状态编码空间再大都不怕。
需要注意，一旦引入时间窗口、过期数据删除这些业务需求，纯摩尔投票法就不够用了，因为候选人和 count 是"无记忆"的，无法精确处理"票过期"的语义。这种情况下可以改用计数数组或加权近似方案。算法再怎么优雅，也要服从业务约束，这是我做了不少数据管道之后最深的体会。
7. 写在最后的实战心得
7.1 我踩过的两个坑
第一次自己实现时，我把判断顺序写反了，先判断 x == candidate，再判断 count == 0。这段代码在多数用例上都能跑对，但遇到 [1, 1] 这种双元素数组时，思路容易绕晕。建议新手实现时严格按"先判空、再判等、最后抵消"的顺序写，逻辑最不容易乱。顺序问题看似小事，在候选人与计数器同时变化的瞬间，很容易埋下隐性 bug。
第二个坑就是忘了二次验证。有个版本的题目不保证多数元素存在，我第一次提交只做了第一遍遍历，样例里刚好有个 [2, 2, 1, 1] 反例，直接 WA。从那以后我养成了习惯：只要题目没说"保证存在"，一律加验证，并且把验证和主流程拆成两个函数，方便单测覆盖。
7.2 面试中怎么回答最容易加分
如果面试官让你写多数元素，我建议回答顺序是：
- 先确认题意，问清楚是否保证存在多数元素。
- 给出哈希表解法，分析 O(n) 空间。
- 追问优化后给出摩尔投票法，手写代码并跑一个例子。
- 主动说出"需要二次验证"以及为什么。
- 如果时间允许，推导一遍不变量证明。
强推第 4 点，因为它往往就是面试官想听的区分点。很多人代码写对但说不出验证的必要性，会让人觉得是背题而非真懂。我在模拟面试里做过观察，能自然讲出"candidate 只是必要条件"的候选人，通常会被追问得更深，但也更容易给出让人满意的推导。
7.3 什么时候别用摩尔投票
摩尔投票法确实精巧，但并非万能。如果你的数据里根本没有超过 n/2 的元素，或者你需要精确频次统计而非"是否存在压倒性多数"，哈希表或排序更合适。摩尔投票不提供任何频次信息，它只回答那个唯一的问题：是否存在多数元素，以及它是谁。看清这一点，才不会在业务代码里为了炫技而引入不必要的复杂度。
我个人现在遇到数组类问题，会先问三个问题：数据能不能一次读完？允许多少额外空间？要的是精确频次还是压倒性多数？前两个问题的答案决定要不要用摩尔投票，第三个问题的答案决定用完之后还要不要补一层统计。想清楚这三个问题，你自然也就能判断什么时候该掏出这个算法，什么时候该把它放回工具箱了。
