做数组题的时候“找出数组中的多数元素”是那种特别容易让人措手不及的题目而专门解决这个问题的摩尔投票算法Boyer-Moore Voting Algorithm也是公认最精妙的线性解法之一。题干本身一句话就能看懂但当你习惯性掏出哈希表统计每个数字出现次数时旁边会有人追问能不能只用一个额外变量把空间复杂度降到 O(1)我第一次听到这个要求时心里完全没底后来弄懂摩尔投票之后才发现答案是如此简单——只需要两个变量一个候选人一个计数器。这篇博文我会从最朴素的问题定义开始把摩尔投票的原理、抵消过程、正确性证明、代码实现和常见变体一整套讲透也会把我在刷题和工程里踩过的坑一并交代清楚。适合刚接触这个算法的同学也适合想彻底搞懂它而不是背模板的进阶读者。1. 多数元素问题先搞懂题目到底在问什么1.1 多于一半和次数最多是两码事多数元素Majority Element在算法题里有严格定义在一个长度为 n 的数组中如果某个元素 x 满足 count(x) n / 2那么 x 就是多数元素。注意这里的比较是严格大于恰好等于一半也不算。数组[1, 1, 2, 2]就没有多数元素因为 1 和 2 都只出现两次等于 n/2 而不是大于 n/2。多数元素和我们平时口语里说的“众数”不是一回事。众数是出现次数最多的那个元素它甚至可以不达到一半而多数元素必须超过一半。比如数组[1, 1, 1, 5, 5, 5, 5, 2, 2]众数是 5出现 4 次但并没有超过 9/2 4.5所以不存在多数元素。反之只要存在多数元素它同时一定是众数。这个区分很关键因为后面会看到摩尔投票算法专门针对“超过一半”这种强约束如果只是找众数它就不灵了。多数元素的定义还隐含一个非常强的性质多数元素的出现次数大于所有其他元素出现次数之和。因为其他元素加一起是 n - count(x)而 count(x) n - count(x)。这个性质是整个算法的支点后面的抵消思想全是从这里推导出来的。1.2 朴素解法的代价对比面对这个题常规思路主要有三四种我先做一个对比哈希表计数用字典记录每个元素出现次数最后扫一遍找次数大于 n/2 的元素。时间复杂度 O(n)空间复杂度 O(n)。排序将数组排序位于中间位置的元素 nums[n/2] 一定是多数元素如果存在。因为多数元素数量过半无论如何都会覆盖中位数位置。时间 O(n log n)空间取决于排序算法。随机化随机选一个元素验证它是否出现超过 n/2 次如果不满足就继续随机选。期望情况下很快命中但最坏情况可能循环很久。分治把数组分成两半递归找各自的多数元素合并时验证。时间 O(n log n)空间 O(log n)。哈希表计数在大多数解题场景里已经够快但问题在于空间。假如现在不是普通数组而是一台服务器连续传来的数据流、一个几十 GB 的文件或者是嵌入式设备里的传感器数据你根本不可能为所有元素建哈希表。O(n) 的空间在这种场景下直接不可用。这正是摩尔投票存在的价值一趟遍历两个变量时间 O(n)空间 O(1)。它放弃了“统计每个元素出现次数”这个中间过程只回答唯一的问题——是否存在多数元素如果存在是哪一个。我在这里先给出一个结论摩尔投票不是用来替代哈希表做统计的它是在内存受限场景下专门利用“超过一半”这个性质做快速判定的巧妙工具。带着这个认知去学算法比单纯背代码有用得多。2. 抵消机制摩尔投票算法的核心直觉2.1 擂台赛比喻候选人和血条摩尔投票的整个过程可以理解成一场擂台赛擂主叫 candidate擂主的“血量”叫 count。遍历数组时每看到一个元素就相当于来了一个挑战者分三种情况处理如果擂主血量归零当前元素直接登台当新擂主血量设为 1如果来的元素和擂主是同一阵营值相等擂主血量加 1如果来的元素是敌对阵营值不同双方各消耗一点血量擂主血量减 1血量归零则擂主下台。用这个比喻算法整个过程只需要记住两件事现在擂台上是谁他还有多少血。这就是空间 O(1) 的由来。为什么这套规则能找到多数元素结论很朴素因为多数元素的“人数”比其他所有阵营加起来都多。擂主可以依次和其他阵营的人一对一消耗其他阵营的人全部耗尽时多数元素阵营至少还有一个人站在台上。哪怕中间有别的阵营暂时领先只要换算成全局的消耗战多数元素因为人多最终一定会站到最后。2.2 为什么可以丢弃当前平局片段理解算法还有一个坎为什么当 count 归零时把当前扫描过的部分直接“扔掉”从下一个元素重新开始没问题其实 count 归零代表这一段里擂主阵营和其他阵营发生了恰好相等的消耗整体处于“平局”状态。去掉这段平局对全局多数元素的判定没有任何影响。原因很简单如果一个元素 M 在整个数组里出现超过一半那么它在这段被丢弃的平局片段里至多也只占一半因为整段是平的反过来在剩下的部分里M 出现的比例只会比整段更高依然超过一半。所以“丢弃平局片段”等于把一个不会影响答案的前缀删掉剩下的子问题依然满足多数元素存在的条件。这一点和括号匹配很相似遇到配对成功就消掉剩余的括号序列保持了原来的性质。摩尔投票每次 count 减到 0就是一次“配对成功”把一段无关紧要的前缀消掉继续处理剩下的数据。想明白这一步后面的正确性证明和 n/k 推广就都顺了。3. 单候选版本的完整实现手把手推演与代码3.1 一个能体现候选更换的完整例子先用一个数组完整推演一遍[2, 2, 1, 1, 1, 2, 2]这个例子的答案是 2出现 4 次大于 7/2 3.5。初始状态candidate Nonecount 0。读到 2count 0candidate 2count 1读到 2和 candidate 相同count 2读到 1和 candidate 不同count 1读到 1和 candidate 不同count 0。此时前四个元素被抵消清零读到 1count 0candidate 1count 1读到 2和 candidate 不同count 0。到这里前六个元素又实现了一轮抵消读到 2count 0candidate 2count 1。最终 candidate 是 2。注意中间 1 曾经短暂成为候选人但又被 2 消耗掉了。表面上看起来好像很不稳定但最后结果恰好正确。再看一个没有多数元素的例子[1, 2, 3]。第一步 candidate1count1第二步遇到 2count 归零第三步遇到 3count 归零后 candidate3count1。最终候选人是 3但它只出现了一次根本不是多数元素。这说明算法第一轮只负责给一个“可疑对象”不能直接当成答案第二轮验证必不可少。这个例子建议各位亲手推一遍能明显感觉到验证阶段为什么不是多余的。3.2 Python、Java、C 实现与简洁写法标准实现如下语言之间的细节差异我会在后面的踩坑部分展开。Pythondef 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 candidateJavapublic int majorityElement(int[] nums) { Integer candidate null; int count 0; for (int x : nums) { if (count 0) { candidate x; count 1; } else if (x candidate) { // candidate 此时必非 null count; } else { count--; } } return candidate; }Cint majorityElement(vectorint nums) { int candidate 0; int count 0; for (int x : nums) { if (count 0) { candidate x; count 1; } else if (x candidate) { count; } else { count--; } } return candidate; }很多地方会把代码压缩成一行更新def majority_element(nums): candidate None count 0 for x in nums: if count 0: candidate x count 1 if x candidate else -1 return candidate简洁写法没有错但我不建议在还不熟悉算法时使用。因为它把if count 0和elif x candidate两个分支合并了初学者在纸上推演时容易忽略候选更换的时机。面试时也是同样道理讲清楚普通版本再提一句“可以用三目压缩”远比直接甩一个一行版本显得扎实。4. 验证阶段候选人不一定是答案这一步决定成败4.1 没有多数元素时算法会返回什么如上面的[1, 2, 3]所示当数组根本不存在多数元素时第一轮结束后 count 可能不为 0candidate 指向的是某个元素但它可能只出现一次。直接返回 candidate 就是一个错误答案。所以完整算法的标准形态是两轮遍历第一轮用抵消机制找出候选第二轮重新统计该候选的出现次数确认它是否真正超过 n/2。如果超过返回候选如果不超过说明数组不存在多数元素返回 -1 或者 null取决于题目约定。带验证的 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 # 第二遍验证 appear sum(1 for x in nums if x candidate) if appear len(nums) // 2: return candidate return -1这里有个细节值得注意len(nums) // 2是整数除法等于 floor(n/2)。要求是 n/2当 n 为偶数时n//2 1 才满足用 len(nums) // 2判断正好覆盖了这一点。例如 n4出现 2 次不算多数appear 2才能通过。4.2 什么时候可以不验证、什么时候必须验证经典在线算法题库里的 Majority Element 一题题目条件里明确写了一句“你可以假设数组非空并且给定的数组总是存在多数元素”。在这种条件下候选必然是答案验证步骤可以省略少一次遍历代码也能更短。这也是大多数教程里只写第一轮的原因。但工程实践里我强烈建议保留验证步骤。原因很简单输入数据的约束取决于上游你无法保证调用方永远传一个必然存在多数元素的数组。一旦数据分布变化没有验证的算法会悄悄返回一个错误候选而且这种错误在线上很隐蔽不容易排查。多遍历一次的时间成本是 O(n)空间成本还是 O(1)这笔买卖非常划算。我把两种场景整理成一张表方便进项目时快速判断场景是否需验证原因题目保证存在多数元素可不验证候选人必为答案题目未作保证必须验证候选可能不是多数元素数据来自外部输入或日志流强烈建议验证数据分布不可控宁可多花 O(n) 时间避免错误结果嵌入式或内存极小场景仍应验证验证只多一次遍历不占额外内存收益很高5. 正确性证明用反证法和不变量说服自己5.1 最直观的优势证明理解证明之前先明确前提真正存在的多数元素 M出现 m 次其他元素一共 n - m 次且 m n - m。也就是说M 阵营的人数严格多于所有反对阵营的人数总和。观察算法的抵消动作每当 count 减一就相当于两个不同阵营的人同归于尽。如果擂主恰好是 M那么这次抵消消耗了 1 个 M 和 1 个非 M如果擂主不是 M则这次抵消消耗的是 2 个非 M 成员M 反而没有受损。注意后一种情况对 M 更有利——因为一个反对 M 的阵营成员可能顺手消耗掉了另一个反对 M 的成员。无论哪种情况M 被消耗的数量永远不会超过非 M 被消耗的数量。而非 M 总量本来就小于 M 总量所以把非 M 全耗完时M 至少还剩一个。因此算法结束时 candidate 必然是 M。这个证明不需要关心中间候选怎么换来换去只抓住“总数上 M 的优势不可能被消耗完”这一点。它解释了算法的本质一对一的消耗规则下绝对多数必然胜出。5.2 不知道多数元素时的不变量表述上面的证明假设多数元素一定存在适用范围主要是题目有保证的场景。如果要处理“可能存在也可能不存在”的一般情况需要更严谨地描述算法维护的不变量。我们可以这样描述扫描完任意前缀后算法给出的 (candidate, count) 代表“这段前缀经过抵消后剩下一部分只由 candidate 构成净计数为 count”。如果再结合全体数据存在多数元素 M 的假设可以证明一个更强的不变量无论处理到哪个位置M 都一定存在于尚未被抵消的部分中或者等于当前 candidate。用反证法可以很简洁假设多数元素 M 存在但算法最终返回的 candidate 不是 M。那么算法的整个过程中一定存在某个时刻把 M 所在的片段“抵消清零”了。抵消清零意味着该片段中任意两个不同阵营成对消耗M 在这个片段里的数量必然不超过片段长度的一半。前面分析过任何一段这样的前缀其内部的 M 数量都不超过非 M 数量。把所有这些被清零的片段累计起来M 的总计数就无法超过数组长度的一半这与 M 是多数元素矛盾。所以最终 candidate 必须是 M。这个不变量版本的证明其实才是通用版本因为它不依赖你提前知道 M 是谁只依赖“M 存在”这个假设。算法的名字叫“投票”但本质上是一个靠对抗消耗来完成筛选的机制理解到这一层面对变形题时会从容很多。6. 扩展变体超过 n/3 和一般 n/k 的多数元素6.1 超过 n/3 的最多有两个双候选版本多数元素的概念可以推广经典的多数元素要求超过 n/2变体题要求找出所有出现次数超过 n/3 的元素。一个很关键的观察是超过 n/3 的元素最多只能有两个因为三个元素如果都超过 n/3它们出现次数之和会大于 n矛盾。因此算法需要维护两个候选和两个计数器。遍历逻辑类似但每一轮要同时照顾两个候选人当前元素等于候选一候选一计数加一否则等于候选二候选二计数加一否则如果候选一的计数为零把当前元素设为候选一否则如果候选二的计数为零把当前元素设为候选二否则两个候选同时减一表示两个候选都和一个外部元素抵消。我用[1, 1, 1, 3, 3, 2, 2, 2]来走一遍正确答案应该是 [1, 2]因为 1 和 2 都出现 3 次大于 8/3 2。读 1候选一为空c11cnt11读 1等于候选一cnt12读 1等于候选一cnt13读 3不等于 c1c2 为空c23cnt21读 3等于候选二cnt22读 2不是 c1 也不是 c2两个计数都非零cnt12cnt21读 2同上cnt11cnt20读 2cnt2 为 0设置 c22cnt21。最终候选是 1 和 2。验证后两者都超过 n/3返回 [1, 2]。注意候选一始终没变候选二中间从 3 换成了 2符合预期。双候选版本的实现代码如下def majority_element_ii(nums): c1 c2 None cnt1 cnt2 0 for x in nums: if x c1: cnt1 1 elif x c2: cnt2 1 elif cnt1 0: c1 x cnt1 1 elif cnt2 0: c2 x cnt2 1 else: cnt1 - 1 cnt2 - 1 # 验证阶段 n len(nums) res [] for c in (c1, c2): if c is not None and sum(1 for x in nums if x c) n // 3: if not res or res[-1] ! c: res.append(c) return res6.2 推广到 k维护 k-1 个候选超过 n/k 的元素最多有 k-1 个这是前面的直接推广。通用实现可以用一个字典保存最多 k-1 个候选每个候选维护计数。遍历时元素已在候选字典中计数加一候选数量不足 k-1加入候选否则所有候选计数减一计数归零的候选移出。因为候选数量最多 k-1空间复杂度是 O(k)k 固定时仍是 O(1)。通用实现如下def majority_elements_k(nums, k): candidates {} for x in nums: if x in candidates: candidates[x] 1 elif len(candidates) k - 1: candidates[x] 1 else: for key in list(candidates): candidates[key] - 1 if candidates[key] 0: del candidates[key] n len(nums) res [] for c in candidates: if sum(1 for x in nums if x c) n // k: res.append(c) return res这个通用版本同样需要验证阶段。比如[1, 2, 3]k2 时它应该返回空列表因为没有任何元素超过一半但第一轮生成的候选可能非空靠验证把它过滤掉。这里再强调一次摩尔投票的变体永远只回答“哪些元素可能超过 n/k”最后的验证必须重新数一遍出现次数。不要试图从候选计数器里直接推断真实频数计数器的值在多次抵消后只是相对关系不代表真实出现次数。这是很多人扩展 n/k 时容易踩的坑。7. 实战踩坑与使用心得7.1 最常见的三个错误第一个错误忘记验证阶段。这个前面反复提过但我还是要单独列出来因为我见过太多人在题目没有保证多数元素时直接返回 candidate然后被边界测试一击致命。请记住摩尔投票完整流程永远是“找候选 验证候选”缺一不可。第二个错误Java 中 candidate 用 Integer 时先比较相等再判断 count0。如果 candidate 初始为 null遇到第一个元素时x candidate会触发拆箱空指针。虽然x candidate这种写法在 count ! 0 时是安全的但保险起见count 0的判断永远应该放在最前面candidate 先落位再谈相等比较。C 和 Python 没有这个问题但分支顺序保持一致读代码的人也更不容易看错。第三个错误双候选版本的候选重复。例如数组元素全部相同有些实现里两个候选会变成同一个元素验证后如果不做去重结果列表里会多出一个重复答案。处理办法是在验证时加一个res[-1] ! c的判断或者用集合辅助。另外补一个比较冷门但确实有的坑字符串匹配领域也有一套叫 Boyer-Moore 的算法和这里的摩尔投票完全不是一回事。名字都带 Boyer-Moore但一个是字符串快速匹配一个是数组多数元素查找。搜资料时记得加上“多数元素”“投票”这类限定词不然很容易看到一长篇字符串匹配的分析白白浪费时间。7.2 摩尔投票不适用的情况和应用场景摩尔投票不是灵丹妙药。如果问题是“找数组里出现次数最多的元素”不管它有没有超过一半都不能用摩尔投票直接解决因为它的整个运作前提就是绝对多数。真要找众数还是老老实实用哈希表或者排序。它的真正优势场景是内存受限、一次遍历的流式数据处理。比如在某个日志分析工具里要从海量日志行中判断某一种异常状态是否占了绝对多数如果每来一行数据都写进哈希表内存迟早被撑爆用摩尔投票两个变量打一遍候选异常类型一秒钟就能出来再补一遍验证即可确认。再比如投票系统的实时计票只看“谁的支持率过半”不需要精确频数摩尔投票也是非常合适的一趟流式筛选器。我个人的体会是这个算法代码短到只有十来行但想把它讲清楚、写对、证明对反而比一些大段代码的题目更考验功底。每次写摩尔投票我都会在心里默念三件事——先更新计数为零的分支再判断相等第一轮只给可疑候选第二遍验证必须补上。这三句话能覆盖绝大多数踩坑场景。按照我的经验学摩尔投票最容易跳过的恰恰是“验证”这一步但最不影响背代码的也是这一步。如果你只是刷题题目保证有答案时可以省如果是在真实系统里用这套逻辑无论数据约束写得多严格我都会坚持把验证加上。毕竟一趟 O(n) 的扫描换一个不会悄悄出错的结果这笔账怎么算都划算。最后留一个小思考给各位如果把摩尔投票和分块思想结合起来每块分别维护候选和计数最后再合并能不能用来处理分布式场景下的多数元素查找想明白这个问题你会对“抵消”这两个字有更深的体会。