摩尔投票法Boyer–Moore majority vote algorithm一道算法题背后的“流式计算”思维如果你处理过巨大日志、超大数组肯定遇到过这种需求在一堆数据里找出“出现次数超过一半”的那个值。内存很紧张数据又不能全部装进HashMap几次遍历也很贵。很多人第一反应是排序或哈希计数但这两招在面对几亿条记录时都显得笨重排序 O(n log n) 只是“忍一忍也能接受”哈希表则可能直接让内存爆掉。这时候摩尔投票法Boyer–Moore majority vote algorithm就浮出来了。这个算法的精妙之处在于它只需要两个变量。一个记“候选人”一个记“票数”。全程只扫描一遍数组时间复杂度 O(n)额外空间 O(1)。更难得的是它的思想极其直白——让不同的元素互相抵消剩下的那个就是潜在赢家。我第一次看到这个解法时愣了一下心想这么简单的东西为什么当年学数据结构没人讲。后来才知道它不只是面试里的“秒杀技巧”在流式统计、分布式数据处理场景里也有实际价值。这篇文章就把摩尔投票法从头到尾拆开从原理、证明、手写实现到找 n/3、n/k 的扩展再到工程落地和常见坑一次讲透。适合准备算法面试的人也适合做海量数据处理、监控统计的工程师。1. 从一个“找众数”的小问题说起1.1 看似简单的题为什么哈希表和排序都不是最优先把问题摆清楚给定一个长度为 n 的数组找出出现次数大于 n/2 的那个元素。题目里通常还会补一句“如果存在请返回它如果不存在返回 -1”。在很多算法题库里它被归为“简单题”但它其实是个很好的思维门槛题。朴素解法有三种思路各有各的别扭。哈希表计数遍历一遍数组把每个元素出现次数记下来时间 O(n)空间 O(n)。如果数组里只有几千个不同的值这当然没问题但数据量大到上亿不同的key可能有千万级别HashMap 的内存开销极其夸张。而且在实际场景里数据往往还在磁盘或网络流中根本没法一次性建出完整哈希表。排序取中位如果存在超过一半的元素排序后它一定落在中位位置。但排序的时间是 O(n log n)对于海量数据来说哪怕只是多一个 log n 的因子都要多花十倍以上的时间。而且不少排序不是稳定原地额外空间也不容忽视。随机化采样随机抽一个元素统计它在全数组中出现次数重复几次。期望时间是 O(n)但不是确定性的最坏情况可能抽很久抽不中目标。工程上能用但面试官往往期望你给一个“确定且干净”的答案。那问题就变成了能不能只遍历一遍同时只用常数空间这个要求听着苛刻但摩尔投票法偏偏能做到。注意这里说的“空间 O(1)”指的是与数据规模无关的固定空间。不管数组里有多少种不同元素我都只用两个变量这是解决海量数据问题的关键前提。1.2 一句大白话所有不同元素都能“同归于尽”摩尔投票法的核心思想可以压缩成一句话不同的元素遇到一起就抵消同一阵营的元素则抱团叠加最后活下来的阵营就是最有力的候选者。怎么理解你可以把数组里的每个元素想象成一个人同一个值代表同一个阵营。算法遍历这些人时维护一个“当前擂主” candidate 和一个“当前擂主的存活人数” count。规则只有三条如果 count 为 0说明当前擂主已经死光把新看到的元素设为 candidatecount 设为 1。如果新元素和 candidate 相同count 加 1相当于同阵营的人加入。如果新元素和 candidate 不同count 减 1相当于两个不同阵营的人同归于尽。听起来像小孩玩“打架”游戏但它的正确性很硬。用数组[2, 2, 1, 1, 1, 2, 2]走一遍立刻能看到效果。已处理元素candidatecount这一轮发生了什么221count 为 02 成为 candidate222同阵营count 加 11211 与 2 不同count 减 1120又来一个 1count 减到 0前面的 2 和 1 全部抵消111count 为 01 成为新 candidate2102 与 1 抵消count 归零221count 为 02 成为新 candidate最终 stopping 在 candidate 2而 2 在这个数组中恰好出现了 4 次超过 7 的一半。整个过程只扫了一遍没有额外容器非常干净。不过这里必须先打个预防针最后得到的 candidate 只是一个“候选人”不代表它一定就是众数。如果数组本身不保证存在超过一半的元素最后活下来的可能是“矮子里拔将军”。为什么需要第二步验证、怎么验证我在第 3 章专门讲。2. 算法完全拆解从原理到数学直觉2.1 两个变量怎么完成“全局占比判断”很多人第一次看到 count 这个变量时会觉得它只是个简单计数器。其实它的真正含义是当前 candidate 相对其他所有元素的“净优势人数”。具体来说在遍历过程的任意时刻可以这样理解当前状态前面已经处理过的所有元素中由于持续的“不同元素配对抵消”剩下了一批未被抵消的元素。这批元素一定全是同一个值也就是当前的 candidatecount 就是这批剩余元素的数量。一旦遇到一个新元素它要么加入这批剩余元素相同值要么与这批剩余元素中的某一个抵消不同值。举个例子数组[2, 2, 1, 1]处理完前四个元素后2 和 1 各有两个两两抵消剩余元素为 0count 回到 0。此时可以说“前面这段已经完全配平”。接下来从新元素开始重新选候选人这并不会丢失已有信息因为抵消操作本身是公平的被抵消掉的每一对都是两个不同的值。这个状态设计非常像“打架”或“配对消消乐”。你可以想象一个战场每个元素是一个战士战士只认自己阵营的标记。任意两个不同阵营的战士相遇会同时倒下同阵营的人站在一起数量累加。摩尔投票法里的 candidate 就是当前战场上唯一还站着的阵营count 就是这个阵营的人数。如果最终存在一个超过半数的阵营无论中间怎么打它的人数足够多不可能被完全消灭。用这个模型去理解算法比背代码有用得多。面试时如果能把“count 的本质是净优势票数”讲出来基本就能让面试官点头。2.2 为什么保证能找出真正的多数一个漂亮的证明口说无凭需要一个严格的证明。假设数组长度为 n存在某个元素 a 出现了 m 次且 m n/2。我们希望证明摩尔投票法最终留下的 candidate 一定是 a。先看算法中的关键操作当 count 大于 0 且当前元素与 candidate 不同时count 减 1相当于“删除”了一个 candidate 和一个当前元素。注意每次删除的两个元素一定是不相同的值。再来想a 出现次数超过一半意味着非 a 的元素总数少于一半。如果把所有抵消操作看成“不同元素配对消耗”那么最坏情况下a 每次都会被拿去和一个非 a 配对。但非 a 的总数不足一半就算它们全都拿来抵消 a也不足以把 a 全部消光。一种更严谨的表述是为了完全消灭 a至少需要 m 次包含 a 的抵消操作因为每一次抵消最多只能消灭一个 a。每次抵消会消耗两个元素所以 m 次抵消至少消耗 2m 个元素。但 m n/2因此 2m n超过数组元素总数矛盾。所以在算法结束前a 不可能被全部抵消最终剩余元素里一定包含 a。而算法保证剩余元素是同一种值这个值就是 candidate所以 candidate 必定是 a。这个证明逻辑很简洁值得记下来。它不依赖任何复杂的数学工具只是利用了“大于一半”带来的配对不等式。2.3 和分治、随机化等解法的底层联系有意思的是摩尔投票法不是孤立技巧。把它和几个常见思路放在一起看能发现它们是同一棵树的枝杈。分治法把数组反复对半切递归求每一半的众数。若两半众数相同就是整体众数若不同就比较两个候选者在全局的出现次数。时间复杂度 O(n log n)。而摩尔投票法相当于把这种“递归抵消”显式地压成了单次遍历用两个变量模拟递归过程中的合并逻辑空间从 O(log n) 降到 O(1)。随机化方法随机挑一个元素统计它是不是超过一半期望 O(n)但最坏情况不确定。摩尔投票是确定性的最坏仍然 O(n)。更一般的高频项估计如果继续推广到“找出现次数超过 n/k 的所有元素”就变成了 Misra-Gries 摘要算法或 SpaceSaving 家族的思路。很多人没意识到摩尔投票法其实是这些算法在 k 2 时的特例。理解了这一点以后遇到“流式 top-k 频率估计”时上手会快很多。这些联系说明了一件事摩尔投票法不是面试官拍脑袋出的偏题而是一个“算法原型”。它背后是一整套“用有限状态概括无限流数据”的思维这也是它后来能进入流式计算、分布式归并领域的原因。3. 手写实现从伪码到可上线的代码3.1 最简单版本认定众数一定存在时的十来行代码很多算法题会给出“输入保证存在众数”的前提。这种场景下实现可以极其精简先跑一遍抵消最后直接返回 candidate省掉第二遍验证。下面是 Python 写法。def majority_element(nums) - int: 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这段代码干了一件很反直觉的事它从头到尾没有统计任何一个元素出现的次数最后却直接给出了主元素。原因就在于第 2.2 节的证明如果存在大于 n/2 的元素它不可能被完全抵消而所有抵消操作又只会留下同一种值所以循环结束后 candidate 就是答案。C 版本同样很短方便和别的语言对照。int majorityElement(vectorint 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; }注意这里 candidate 初始化为 0如果数组里真的可能出现 0这种写法也不会出错因为 count 为 0 时马上会被当前元素覆盖。不过工程上我建议用更中性的写法比如用None或一个哨兵对象避免和业务数据混淆。3.2 第二遍扫描为什么省不掉如果题目没说“一定存在众数”只给你一个普通数组那返回 candidate 就可能踩坑。看两个反例。[1, 2, 3]跑一遍摩尔投票。1 先成为 candidate2 抵消它3 成为 candidate最终返回 3。但 3 只出现了一次根本没过半。[1, 1, 2, 2, 3]前四个元素两两抵消3 最后成为 candidate同样不是众数。问题出在“净优势”不等于“绝对数量”。candidate 只是在抵消游戏中活到了最后但如果数组里根本没有一个阵营人数过半活到最后的不代表任何意义。这就是为什么通用版本的代码必须加一个验证阶段再遍历一次数组统计 candidate 的实际出现次数如果大于 n/2 才返回否则说明不存在众数。def majority_element_with_check(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 -1这里有一个非常隐蔽的小坑判断条件是total len(nums) // 2不是。题目要求的是“超过一半”等于一半不算。比如[1, 1, 2, 2]1 出现 2 次n 的一半正好是 2不能算众数。如果这里写成就会错误地返回 1。我在面试里见过好几个同学在这种细节上翻车代码逻辑整体没问题就是差一个符号。3.3 边界条件与一行代码里的坑写摩尔投票法时边界情况很容易被忽略。我自己总结了几个必须测的用例。空数组循环直接跳过candidate 是初始值。如果题目要求找不到返回 -1记得预先处理len(nums) 0。单个元素比如[7]循环结束 count 1candidate 7验证阶段 7 出现 1 次大于 0.5返回 7。全相同元素[5, 5, 5, 5]candidate 从头到尾是 5count 一直累加到 4验证通过。交替抵消[1, 2, 1, 2]没有元素过半。算法最终 candidate 可能是 2验证阶段发现它只出现 2 次不大于 n/2返回 -1。另外如果语言是 Pythoncandidate 初始值用 None 时要小心数组里真的包含 None 值。更稳妥的做法是先用一个哨兵标记“空位”或者只处理类型明确的数值数组。C/Java 里可以设置候选为数组首元素count 初始为 0这样也能避免“谁都不认识”的初始态问题。这些小细节不会影响算法本身但直接影响代码健壮性。4. 复杂度对比与进阶变体4.1 时间 O(n)、空间 O(1) 到底意味着什么把摩尔投票法和其它思路放在一张表里差距一目了然。解法时间复杂度空间复杂度单遍扫描备注HashMap 计数O(n)O(n)是不同元素多时内存开销大排序取中位O(n log n)O(1)~O(n)否时间慢视排序实现随机采样验证期望 O(n)O(1)否最坏不确定分治合并O(n log n)O(log n)~O(n)否递归额外空间摩尔投票法O(n)O(1)是第二遍验证仍O(n)“O(1) 空间”在海量数据场景里是决定性的优势。数据量达到十亿级别时O(n) 的空间意味着要上百 GB 内存而 O(1) 就是几十字节。单遍扫描也很重要很多数据源是磁带、网络包、日志文件只能顺序读取一次不能像数组那样随机访问。所以摩尔投票法天然适配“流式环境”这也是它能从算法题库走进真实系统的原因。4.2 从找 n/2 延伸到找 n/3两个候选人如果题目改成“找出所有出现次数超过 n/3 的元素”摩尔投票法还能用吗能而且思路是同一个只是从“两个不同元素互相抵消”升级成“三个不同元素一起抵消”。先想清楚一个前提超过 n/3 的元素最多只能有两个。因为如果有三个元素都超过 n/3它们总出现次数就会超过 n显然不可能。所以算法只需要维护两个候选人和两个计数器。遍历数组时按顺序执行以下规则如果当前元素等于 candidate1则 count1 加 1。如果当前元素等于 candidate2则 count2 加 1。如果 count1 为 0把当前元素设为 candidate1count1 1。如果 count2 为 0把当前元素设为 candidate2count2 1。否则说明当前元素和两个候选人都不同触发一次“三方抵消”count1 减 1count2 减 1。最后再遍历一次统计两个候选人的真实出现次数超过 n/3 的加入结果。def majority_elements(nums): n len(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, cnt1 x, 1 elif cnt2 0: cand2, cnt2 x, 1 else: cnt1 - 1 cnt2 - 1 res [] for c in (cand1, cand2): if c is not None and nums.count(c) n // 3: res.append(c) return res这里最容易写错的点是顺序。很多人会先把“空位判断”放在前面导致同一个元素被误设为新候选人。比如数组[1, 1, 1, 2, 2, 2, 3]如果某个 x 已经和 cand1 相同却先走了空位逻辑就可能把候选搞乱。正确顺序一定是“先匹配已有候选人再填空位最后才整体减票”。这个顺序背后逻辑是同阵营的人必须优先加入不能让他另立山头。4.3 一般化找超过 n/k 的所有元素把 n/2 和 n/3 再往前推一步如果要求找出所有出现次数超过 n/k 的元素怎么办答案是维护 k-1 个候选人和 k-1 个计数器。原理和 n/3 完全一样只是“几方混战”的规模变大了一个元素命中已有候选人时对应计数器加 1如果没命中但有空位就填进去计数器置为 1如果没命中且没有空位就把所有候选人的计数器同时减 1。为什么最多 k-1 个反证法如果有 k 个元素都超过 n/k它们总出现次数大于 k × (n/k) n矛盾。所以结果集大小有天然上界。这个算法的时间复杂度是 O(nk)。k 如果是个固定常数比如 5 或 10可以当作 O(n) 看空间 O(k) 也是常数级。这里用到的就是 Misra-Gries 摘要算法的核心逻辑。很多做大数据流统计的同学会对“在线找高频项”的问题头疼其实摩尔投票法就是它最朴素的起点。我自己在实现类似功能时也是先从这个框架出发再根据业务需要加误差控制。5. 工程落地流式数据、分布式与题目扩展5.1 单遍扫描 常驻内存天然适合流式计数算法题学会之后如果在业务里遇到“海量数据中找占比超过一半的值”摩尔投票法是很好的起点。举个例子网关每分钟接收数百万条请求每条请求带一个返回码。想判断某个时间段内“哪种返回码占比超过 50%”。如果用 HashMap 统计所有返回码内存会随返回码种类数增长如果排序则根本无法在流上完成。摩尔投票法只需要两个变量每来一条请求更新一次内存占用恒定。等窗口结束时候选返回码已经算出来了再用另一条路径统计它的真实出现次数即可。不过必须强调一个工程上的边界流式环境中数据是无限的算法并不记忆过去所有元素所以如果数据流里根本不存在过半数元素最终候选值可能频繁漂移。这种情况下单纯靠摩尔投票法无法给出可靠结论通常的做法是在固定时间窗口内运行算法窗口结束就输出当前候选将“是否存在众数”这个问题交给业务规则比如只关心候选值出现比例的近似估计对候选值单独开一个计数器跟踪它在整个流里的真实频次。这里也涉及一个理论限制任意流式算法如果要精确求出“绝对占比超过一半”的元素常数空间是不够的因为不同元素可以无限多。摩尔投票法保证的是“如果存在众数最终候选一定是它”而不是“实时告诉你每个时刻的真实频次”。理解了这一点就不会在业务里错误地依赖它。5.2 跨机合并分片跑一遍再汇总对决另一个让我觉得摩尔投票法很酷的地方是它可以并行化。它不只是能“单机单遍跑”还能分片合并。假设一个数组被切成两半分别用摩尔投票法处理。每个分片得到自己的结果是个二元组(candidate, count)表示“这段数据抵消后剩余的一方及其人数”。合并两个分片摘要时规则是如果两个候选相同合并后的候选就是它人数相加如果候选不同比较两边剩余人数人数多的获胜新人数是两者之差如果恰好相等则完全抵消合并结果为空。比如分片 A 返回(x, 3)分片 B 返回(y, 5)那么合并后的整体摘要就是(y, 2)。直观理解A 段还剩 3 个 xB 段还剩 5 个 y放一起就让它们先对战y 多出 2 个所以整体剩下 y 阵营的 2 个。这个性质让摩尔投票法在分布式环境里变得很有用。只要把数据按某种 key 分片每台机器只对本地片段跑一遍得到摘要然后汇总合并就能得到全局候选。更妙的是这个过程可以做成树形归并处理几亿条数据时非常高效。不过合并之后仍然绕不开验证。比如[1, 2, 3]分成[1, 2]和[3]前者抵消为空后者摘要(3, 1)合并结果是(3, 1)但 3 显然不是众数。所以分布式版本的正确流程永远是归并出全局候选后再独立统计该候选的全局出现次数。5.3 一个更综合的实战例子把单机、流式、分布式串起来可以设计一个比较完整的方案。假设有一个超大文件每行一个用户 ID需要找出出现次数超过总行数一半的那个 ID。文件太大不能整个读进内存。第一步单机流式扫描用一个 FileReader 逐行读取只维护 candidate 和 count 两个变量。文件读完得到候选 ID。第二步验证扫描再读一遍文件统计这个候选 ID 出现了多少次。由于第一遍扫描已经得到了候选第二遍只需要一路累加一个计数器即可内存仍然是常数。如果统计结果大于总行数的一半就输出它否则结论是“不存在这样的 ID”。第三步如果文件已经存在多个副本或分布在多台机器上可以改成并行流程每台机器独立跑第一步输出本地摘要(candidate, count)然后汇总到一台机器按合并规则归并出全局候选再让各机器协同验证候选出现次数。整个过程没有使用任何 HashMap没有排序没有把数据载入内存。在日志分析、用户行为统计这类“高基数、低容忍内存”的场景里这套流程比把几千万个 key 塞进内存的方案稳得多。6. 常见问题与避坑手册6.1 面试/笔试中容易被卡住的三道关我把平时见到的经典追问整理成几个速查问题每个问题的答案都能反映对算法的理解深度。问题简答最后留下的 candidate 一定就是众数吗不一定。只有在输入保证存在过半数元素时它才是众数任意数组场景下必须先验证再下结论。遍历到 count 0 时重新开始会不会丢掉重要信息不会。count 0 表示之前所有剩余元素已经被不同元素配对抵消配对是公平的不偏向任何值。能不能用这个方法找 n/3 的众数可以但最多两个候选。维护两个计数器规则是“三个不同元素一起抵消”。更一般地n/k 规模需要维护 k-1 个候选。面试官如果追问“为什么 count 减到 0 后前面的数据就像没发生过一样”最好的回答方式是讲清楚配对抵消每一步抵消操作都是把两个不同的元素从“待统计池”里删除而这种删除不会改变某个阵营是否过半的性质。如果有一个阵营真的过半它在任意一轮抵消中被消耗的速度不可能超过它增长的速度。6.2 手写代码时的四个经典错误看别人代码时感觉简单自己动手写就容易翻车。以下四个坑我基本每次帮人 review 都能碰到。错误类型症状原因与修正if 顺序写反例如先判断x candidate再判断count 0当 count 为 0 时仍可能减票导致 count 变负数必须把count 0的判断放在最前面。count 为 0 时直接换 candidate不走后续逻辑。验证时用 len // 2在[1,1,2,2]这类用例上返回错误结果题目要求“超过”一半所以必须是。认为 candidate 中途不能变以为 candidate 就是最终答案不能更新实际算法里每当 count 归零candidate 都会被替换更新 candidate 是算法的关键步骤不是异常情况。n/3 版本先填空位、后判断命中同一元素可能同时被当作新候选导致计数器错乱必须按照“命中已有候选人 → 填空位 → 全体减票”的顺序执行。这四条里第一、四条最隐蔽因为它们不会导致语法错误而是让结果在某些用例上悄悄翻车。建议写完代码后至少跑这三组用例[]空、[2, 2, 1, 1, 1, 2, 2]有众数、[1, 2, 3]无众数。能一次性通过基本就稳了。6.3 写在最后一点个人的实操体会我最初接触到摩尔投票法时第一反应是“这也能行”后来在日志分析里真正用了一次才发现它的价值不在“面试背题”而在“把复杂度从不可能降到可能”。工程上遇到“超大流 找主流”的问题我现在的第一反应已经不是 HashMap 了而是先问自己要不要用抵消思想候选值能不能接受二次验证如果能摩尔投票法往往就是最优解。有几条经验是踩过坑之后才悟出来的。一是千万别省验证阶段写代码时多写一个循环不丢人丢人的是线上返回了一个错误的“众数”。二是解释算法时一定要从“配对抵消”说起不要上来就背代码只有理解了抵消的语义遇到变体题才不会慌。三是扩展思路比孤立记忆重要从 n/2 走到 n/3、n/k其实就是同一个思想在不同规模下的延伸。如果你哪天在流式场景里需要找 top-k 高频项会发现摩尔投票法那套“固定数量候选人 多路抵消”的思路居然还能继续发光。
