LeetCode 169. 多数元素：Boyer-Moore 投票算法的魔术与证明

多数元素（LeetCode 169，Easy）是一道表面极易、内核极妙的题：找出数组中出现次数超过一半的元素。哈希表计数 O(n)/O(n)、排序后取中位 O(n log n)/O(1 或 n)——都满足部分约束。而题目的进阶追问是：O(n) 时间 + O(1) 空间——同时满足的唯一解法是 Boyer-Moore 投票算法：五行代码，直觉如魔术，正确性证明却极其干净。本篇把魔术和证明一起讲清。

算法：五行代码的「对抗消耗」直觉

算法：维护一个候选 candidate 与计数 count。遍历数组：count 为 0 时，把当前元素设为候选、count 置 1；否则——当前元素等于候选则 count 加一，不等于则 count 减一。遍历结束，候选即答案。

def majority_element(nums: list[int]) -> int:
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

直觉解释：把过程想象成「对抗消耗」——多数元素的一个实例与任意一个其他元素配对抵消（count 的加减就是配对）。多数元素出现超过一半（> n/2），无论其他元素怎么排列组合着消耗它，它至少还有一个实例活到最后：最坏情况下，其他所有元素两两之间也互相消耗，剩下的仍是多数元素的实例。算法执行结束时的 candidate，必然是多数元素。

正确性证明：两行配对的不变量

面试官若追问「为什么是对的」，给一个严格的论证。论证（配对视角）：把遍历过程重新叙述为——算法实际上把数组划分成若干段，每段内部发生「不同元素的两两抵消」；count 归零的每个「段」，段内的元素恰好两两不同（每有一个非候选就有一个候选被抵消），因此每个「归零段」中多数元素与非多数元素的数量相等——多数元素的「多数优势」完整地保留在归零之后的剩余部分里。对剩余部分归纳：剩余数组中多数元素仍然严格占多数（原来的多数减去相等的消耗，仍多于剩余的其他），且算法在剩余部分上继续执行同样的过程。归纳到数组末尾：最后的候选必然是多数元素。这个证明的关键句：「每个 count 归零的段中，候选与非候选一一配对抵消，多数优势只在未归零的尾部保留」——面试中说出这一句，比背五行代码更有说服力。

边界与推广：验证义务、失效边界与进阶变体

必须强调的前提：Boyer-Moore 的正确性依赖「多数元素严格超过一半」的题目前提——若没有多数元素（最高的出现次数 ≤ 一半），算法返回的候选是无意义的（题目保证存在多数元素所以直接返回；若前提不保证，需要第二遍遍历验证候选的计数是否真的过半——O(n) 时间 O(1) 空间，仍然满足约束）。这个「验证义务」是算法失效边界的教学重点：把 Boyer-Moore 用在「无多数元素」的数据上而不验证，是真实工程中的 bug 来源。推广一：出现超过 n/3 的元素（LeetCode 229，求所有出现超过三分之一的元素）——结论：这样的元素至多两个，维护两个候选 + 两个计数的对抗（第三个不同元素同时消耗两个候选的计数），最后同样第二遍验证两个候选——从「一个候选」到「两个候选」的推广，展示这类「计数对抗」方法的扩展模式。推广二：流式场景——多数元素的流式检测（数据流只能过一遍、内存有限）是 Boyer-Moore 的天然应用场景，这是它相对哈希计数的真实工程优势。失效边界之外还要知道：若题目改为「出现次数最多的元素」（非多数），Boyer-Moore 失效（没有「超过一半」的结构保证），退回哈希计数——算法与前提的绑定关系，是这道 Easy 题最大的教学价值。

反例构造练习：亲手制造 Boyer-Moore 的失效数据

「验证义务」的最佳掌握方式是自己动手构造反例——给一个无多数元素的数组，看 Boyer-Moore 返回什么。构造练习：[1, 2, 3]（三个都只出现一次）——模拟：candidate=1, count=1 → x=2 抵消 count=0 → candidate=3, count=1 → 返回 3——但 3 只出现一次，多数元素不存在，返回值毫无意义。再构造：[1, 2, 1, 2]（1 与 2 各两次，无超过一半者）——candidate=1, count=1 → 2 抵消 count=0 → candidate=2, count=1 → 1 抵消 count=0 → candidate=2, count=1 → 返回 2——2 出现两次恰好一半（不是「超过」），返回值依然无效。两个反例的共同模式：count 归零的时机落在数组尾部，最后的候选只是「最后一段的幸存者」——幸存者≠多数者，这是「验证义务」的机制性来源。第二遍验证的实现：统计候选的真实出现次数（Counter 或一遍循环），超过 n/2 才返回、否则返回「无多数」标记——五行代码，把「可能错误」变成「确定正确」。这个练习的迁移价值：任何「利用问题结构保证」的算法（本库 Boyer-Moore、缺失的第一个正数），都值得亲手构造一次「前提不满足」的反例——反例构造是理解算法适用边界的最快路径。

Boyer-Moore 的流式地位：从一道题到一个研究方向

Boyer-Moore 投票算法在流式算法（streaming algorithms）的研究版图里有一个正式的名字归属：它是「确定性单遍、亚线性空间」算法的最早样本之一。流式算法的核心约束：数据只能过一遍（或极少遍）、内存远小于数据量（sublinear）——多数元素检测是这个问题域的「Hello World」；它的推广（出现超过 n/k 的元素，需要 k-1 个候选——本库 n/3 的双候选推广的一般化）就是著名的 Misra-Gries 算法（1982 年，与 Boyer-Moore 的推广同期独立发现）——k-1 个候选互相消耗的框架完全一致。流式算法的更广图景：频率估计（Count-Min Sketch——本库语境的近似计数）、不同元素计数（HyperLogLog——本库语境的基数估计）、以及重元素的持续追踪——这些「 sketch 数据结构」是大数据处理的基建（本库 RAG 语料审计的语境：超大规模语料的「大概频率」正是 sketch 的用武之地——精确审计不可行时，sketch 给出可辩护的近似）。一道 Easy 题连接的研究纵深：从五行代码的投票算法出发，通向的是流式算法的整个研究版图——算法题的「 Easy」标签，从来只代表输入约束的简单，不代表思想的深度。

多数元素的「流式检测」：Boyer-Moore 在大数据场景的定位

Boyer-Moore 的流式检测能力使它在大数据场景有独特的工程地位。设想一个场景：一条数据流持续到来，你需要在 O(1) 内存中维护「到目前为止的多数元素候选」——哈希表方案需要存所有元素的计数（内存随种类增长），Boyer-Moore 只需要两个变量（候选与计数）。当然，它的局限也很清晰：没有「超过一半」的结构保证时，返回值无意义；且不能回答「第二多的元素是什么」。工程上的正确定位：它是「流式频繁元素检测」的入门算法——更复杂的场景（频繁元素 Top-K、基数估计）有对应的进阶算法（Misra-Gries、Count-Min Sketch、HyperLogLog）——但它们的「候选消耗」核心思想全部可以追溯到 Boyer-Moore 这道 Easy 题的五行代码。一道题连接一个研究方向，这就是算法教学的最佳样本。

多数元素的「结构保证」思考

Boyer-Moore 的前提多数元素存在在现实中的对应场景值得思考——它在什么时候真的成立。天然成立的场景：某些共识协议的投票（拜占庭容错的超过三分之二诚实节点假设——虽然阈值不同但多数的结构性保证是协议设计的核心）。不成立的场景是大多数：真实数据 rarely 有某个值严格超过一半——所以 Boyer-Moore 在工程中的直接应用其实很少它的价值几乎全在教学与理论层面：它演示了 O(n) 时间 O(1) 空间的极致优化是如何通过利用结构性保证达成的——这个方法论在流的频繁元素检测等工业算法中有广泛的应用。

多数元素的结构保证思考：从一道题到一个研究方向

Boyer-Moore 投票算法在流式算法的研究版图里有一个正式的名字归属：它是确定性单遍亚线性空间算法的最早样本之一。流式算法的核心约束：数据只能过一遍或极少遍、内存远小于数据量——多数元素检测是这个问题域的入门案例。它的推广（出现超过 n/k 的元素需要 k-1 个候选——本库双候选推广的一般化）就是著名的 Misra-Gries 算法。流式算法的更广图景：频率估计、不同元素计数、以及重元素的持续追踪——这些 sketch 数据结构是大数据处理的基建。一道 Easy 题连接的研究纵深：从五行代码的投票算法出发通向的是流式算法的整个研究版图——算法题的 Easy 标签从来只代表输入约束的简单不代表思想的深度。

小结

这篇收成四条：Boyer-Moore 五行代码——候选与计数，不同元素互相抵消，多数元素必然幸存；正确性的关键句——「每个 count 归零的段中候选与非候选一一配对，多数优势只在未归零尾部保留」，归纳即证；前提是「严格超过一半」——无此保证时必须第二遍验证候选的计数，把 Boyer-Moore 用在无多数数据上不验证是工程 bug 来源；推广到「超过 n/3」用双候选双计数，流式场景是它的天然主场，而「出现最多」（非多数）则完全失效退回哈希。这道 Easy 题的教学价值超过多数 Medium：它演示了「利用问题的结构性保证（多数存在）换取空间上的极致优化」——算法设计的进阶，常常就是发现并利用这样的隐藏结构。

参考资料

LeetCode 169. Majority Element —— 题目与官方题解（Boyer-Moore 的标准出处）
Boyer, R. & Moore, J. (1991). MJRTY — A Fast Majority Vote Algorithm —— 原始论文
LeetCode 229. 求众数 II —— 双候选的推广题