摩尔投票法Boyer-Moore majority vote algorithm是我在刷数组类题目时见过的最精巧的 O(1) 空间解法之一。它的任务很具体在线性时间内只用常数级额外空间找出数组中出现次数超过 n/2 的多数元素。整段核心代码不过十行左右但背后的抵消逻辑、边界判断和证明思路藏着一整套值得拆解的细节。这篇文章想把算法从原理到实现、从证明到扩展讲透适合准备算法面试的人也适合在实际数据处理中需要省内存的人。只要你有过被哈希表空间占用困扰的经历这篇内容应该能给你一个足够顺手的替代方案。1. 多数元素到底在找什么定义先行1.1 一个容易被忽略的前提算法领域有个习惯说法出现次数最多的元素就是多数元素。这句话在多数情况下不算错但在摩尔投票法的语境下必须抠字眼。多数元素的定义是出现次数严格大于 n/2 的元素而不是频次最高。举个例子数组 [1, 2, 2, 3] 里频次最高的是 2出现了 2 次n4n/222 不大于 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 设为 xcount 设为 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。开始遍历当前元素candidatecount操作说明221count 为 0直接选 2 作候选人222与候选相同count 1121与候选不同count -1120与候选不同count -1归零111count 为 0换候选人 1210与候选不同count -1归零221count 为 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]55单元素天然满足 n/2[1, 2, 3]取决于遍历顺序无第一遍后必须验证否则会误报[1, 2, 2, 1]取决于遍历顺序无两个元素各出现 n/2 次没有多数元素第四种情况很有意思1 和 2 各出现两次n4没有任何元素严格大于 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 换成了 1count 为 1。这段区间里2 出现 2 次1 出现 3 次把 2 的 2 张票和 1 的 2 张票配掉还剩 1 张 1 的票和 count1 吻合。遍历前 6 个元素后candidate 是 1count 是 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 的元素或者你需要精确频次统计而非是否存在压倒性多数哈希表或排序更合适。摩尔投票不提供任何频次信息它只回答那个唯一的问题是否存在多数元素以及它是谁。看清这一点才不会在业务代码里为了炫技而引入不必要的复杂度。我个人现在遇到数组类问题会先问三个问题数据能不能一次读完允许多少额外空间要的是精确频次还是压倒性多数前两个问题的答案决定要不要用摩尔投票第三个问题的答案决定用完之后还要不要补一层统计。想清楚这三个问题你自然也就能判断什么时候该掏出这个算法什么时候该把它放回工具箱了。