★ FEATURED ARTICLE 当你在面试或刷题时碰到“找出数组中出现次数超过一半的数”第一反应可能是排序、哈希表或者排序后再取中位数。排序是 O(n log n)哈希表是 O(n) 时间但 O(n) 空间。而有一类问题要求在O(1) 空间、O(n) 时间内搞定它这时候就该轮到 Boyer–Moore 摩尔投票法登场了。摩尔投票法最早由 R. S. Boyer 和 J S. Moore 提出最初是一个解决“流式数据中出现频率超过一半的元素”的算法。因为它只需要维护一个候选值和计数器所以空间占用极小尤其适合数据量巨大、无法一次性装入内存的场景。今天这篇文章我会从直觉到证明、从模板代码到实际变形题、从面试踩坑到工程场景把这个算法彻底拆开。1. 摩尔投票法到底是解决什么问题的1.1 问题定义的“一半”到底意味着什么先明确一下我们要处理的问题给定一个长度为 n 的数组其中某个元素出现的次数严格大于 n/2也就是超过一半要求找出这个元素。“严格大于一半”这个条件是整套算法的命门。注意是“大于”如果只是等于一半摩尔投票法不一定能给出正确答案。这一点在后面的证明里会体现得很清楚。举个例子[2, 2, 1, 1, 1, 2, 2] 中 2 出现了 4 次4 7/2所以答案是 2。这个问题也叫 Majority Element在各类题库和面试中很常见但很多人只知道“用摩尔投票”并不清楚它为什么能在一个变量、一个计数器的情况下做到“抵消”出正确答案。理解摩尔投票法最舒服的方式不是直接背代码而是先把它想象成一场“打仗”或“投票抵消战”每个元素都是一名士兵不同阵营的士兵两两相遇就同归于尽最后剩下来的那个阵营就是人数超过一半的阵营。如果某个阵营人数超过总数一半那么无论怎么两两抵消最后一定还剩该阵营的人。这个直觉很朴素但它遗漏了一个关键点摩尔投票法本质上不是“两两抵消”而是“不同元素之间互相抵消”。代码里只会维护一个候选者和一个计数器遇到相同元素计数加一遇到不同元素计数减一减到零就换候选人。这个过程可以抽象成“当前候选人正在被一群反对者消耗”。1.2 为什么不用哈希表很多人第一反应是哈希表统计每个元素出现次数最后再找次数最多的。哈希表在数据规模小的时候完全没有问题代码也直观。但它有两个痛点空间复杂度是 O(n)如果你处理的是几十亿条 IP 访问日志、上亿个用户 ID哈希表可能会撑爆内存。如果数据是流式的元素一个接一个到达你不可能等全部数据到手再统计但摩尔投票法天然支持流式处理来一个处理一个不需要回看。摩尔投票法最吸引人的地方就是它只用了两个变量候选值 candidate 和计数器 count。不管数组多大空间固定这种“常数空间”的算法在工程中意味着你可以在一个极小的内存环境里完成任务比如嵌入式设备、流式计算节点。2. 从直觉到代码算法核心思路拆解2.1 遍历阶段的两个动作整个算法只有一次遍历全程干两件事当 count 为 0 时把当前元素设置为候选者 candidate并把 count 设为 1。当 count 不为 0 时比较当前元素和 candidate相同则 count 加 1不同则 count 减 1。我先把最经典的 Python 实现放出来咱们对着代码聊。def majority_element(nums): candidate None count 0 for num in nums: if count 0: candidate num count 1 elif num candidate: count 1 else: count - 1 return candidate就这么几行。遍历结束后 candidate 就是多数元素。但如果题目没有告诉你可以直接返回 candidate而是说“如果不存在多数元素返回 -1”那你还得再遍历一次确认 candidate 的出现次数确实超过 n/2。这个二次确认在工程上几乎必做因为算法本身在没有多数元素时会给出一个不一定正确的“幸存者”。2.2 消除反对者的过程模拟我们来手动跑一个例子数组[1, 2, 3, 2, 2, 2, 1]遇到 1count 为 0candidate1count1。遇到 2与 candidate 不同count 减为 0。遇到 3count 为 0candidate3count1。遇到 2与 candidate 不同count 减为 0。遇到 2count 为 0candidate2count1。遇到 2与 candidate 相同count2。遇到 1与 candidate 不同count 减为 1。结束candidate2。有点意思前面 1、2、3、2 互相抵消看似“浪费”了一些 2但因为 2 的总数超过一半2 最终还是剩下来了。整个过程就像在一场混战中两个不同阵营相遇就同归于尽多数阵营总会有人活到最后。你仔细想一下这其实是在维护一组“尚未被抵消掉的配对”count 表示当前 candidate 阵营在“未配对阵营”中的净胜人数。每遇到一个不同的元素就和当前候选者中的一个配对抵消。2.3 为什么 count 减到 0 要更换候选者当 count 减到 0说明当前候选者已经被完全抵消掉了之前配对过程中所有以它为候选者的“净胜优势”没了。此时继续保留它没有意义因为如果它真是多数元素后面一定还会再次出现并把 count 拉起来如果它不是那换掉也理所当然。这个“归零换人”的设计非常精妙它让候选者不止一个而是随着遍历动态变化。像上面的例子里1、3 都当过候选者最后才轮到 2。每个候选者在任期间都代表“当前已扫描部分里最有可能成为多数元素的阵营”。3. 正确性证明为什么这样最后能剩下多数元素3.1 核心不变量抵消配对模型要证明摩尔投票法的正确性最直观的方式是把它看成一个“配对抵消”的过程。假设数组里多数元素为 M出现次数为 m总长度为 nm n/2其他所有元素的个数加起来小于 n/2。在算法的任意一步count 可以理解成“当前候选者 M 或非 M 阵营中未被抵消的人数”。关键性质算法中的每一次 count 减 1都意味着一个候选者和一个非候选者配对抵消。在这一对里如果候选者是 M那么被抵消掉的元素里包含一个 M 和一个非 M如果候选者不是 M那么被抵消掉的两个元素都不是 M。现在考虑所有“配对抵消”的回合再加上最终可能剩余的未配对元素。最终剩余的 candidate 如果是 M那万事大吉。最终剩余的 candidate 如果不是 M这意味着所有 M 都被配对抵消掉了。但在任何一对抵消组合里最多只有一个 M因为配对双方一定不同而每一对里至少有一个非 M。因此要抵消掉所有 m 个 M至少也需要 m 个非 M。也就是说总数 n ≥ 2m这与 m n/2 矛盾。这个证明有点绕但结论非常干净只要存在超过 n/2 的元素它在所有抵消结束后一定还有剩余而且由于抵消双方不同剩余的那个单一元素只会是 M不可能是其他元素混进来的结果。3.2 为什么“等于一半”时可能失效如果多数元素出现次数正好 n/2能不能保证正确不能。比如 [1, 1, 2, 2]n41 出现 2 次等于一半。遇到 1candidate1count1。遇到 1count2。遇到 2count1。遇到 2count0。最后 candidate1count0。此时返回的是 1但 1 并不严格大于一半题目如果要求严格大于这个答案虽然碰巧“对”但如果换成 [1, 2, 2, 1]遇到 1candidate1count1。遇到 2count0。遇到 2candidate2count1。遇到 1count0。最后 candidate2count0。又会返回 2结果就不确定了。所以“严格大于 n/2”不是一句废话它直接决定算法输出是否一定正确。在实现中如果你不确定输入是否满足条件就必须做第二遍扫描确认。3.3 第二遍验证的必要性实际业务里你拿到的数据往往不保证“一定存在多数元素”。比如统计一个论坛里发帖数过半的用户可能根本没有这样的用户。这时候第一遍跑出的 candidate 只是“嫌疑犯”必须再扫一遍统计它的真实出现次数超过 n/2 才接受。验证代码也很简单def majority_element_strict(nums): candidate None count 0 for num in nums: if count 0: candidate num count 1 elif num candidate: count 1 else: count - 1 # 第二次遍历确认 freq sum(1 for num in nums if num candidate) if freq * 2 len(nums): return candidate return -1注意判定的写法freq n/2为了避免浮点误差写成 freq * 2 len(nums)。4. 不同语言的实现模板与细节对比4.1 Python 实现与细节Python 里直接用 for 循环就很好不需要过度优化。但我建议你写成一个函数而不是裸代码方便复用。特别注意 candidate 的初始值在 Python 里用 None 没问题但如果数组元素本身可能为 None 就要小心不过实际场景中很少遇到。下面是带类型标注的版本from typing import List, Optional def majority_element(nums: List[int]) - Optional[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 candidate4.2 C 实现与细节C 要注意 int 溢出问题但 count 最大不会超过 n所以用 int 足够。泛型写法可以兼容 int、long、string 等类型。#include vector int majorityElement(const std::vectorint nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; count 1; } else if (num candidate) { count; } else { --count; } } return candidate; }如果数组里可能没有多数元素第二次遍历统计次数int majorityElementStrict(const std::vectorint nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; count 1; } else if (num candidate) { count; } else { --count; } } int freq 0; for (int num : nums) { if (num candidate) freq; } if (freq * 2 (int)nums.size()) return candidate; return -1; }4.3 Java / JavaScript 实现要点Java 的写法跟 C 几乎一样就不贴完整代码了。JavaScript 里唯一要注意的是 NaN如果你用if (count 0)判断候选值是 NaN 时会出问题因为 NaN ! NaN。一般刷题和业务里不会拿 NaN 当数组元素但你在用通用框架时要留个心眼。还要提醒一点很多人为了“炫技”会把摩尔投票法封装得很复杂。其实这个算法就是两三行逻辑简单直接才是正道。5. 摩尔投票法的变形与扩展不只是求超过一半5.1 求出现次数超过 n/3 的元素这是最经典的扩展题。要求找出所有出现次数大于 n/3 的元素这样的元素最多只有两个。怎么证明最多只有两个如果三个元素的次数都大于 n/3那么总数就大于 n矛盾。所以结果最多两个。这时需要维护两个候选者和两个计数器。过程还是摩尔投票的推广当新元素与 candidate1 相同就 count1 加一与 candidate2 相同就 count2 加一如果 count1 为 0 就把 candidate1 设为当前元素count2 为 0 就设置 candidate2如果都不匹配count1 和 count2 同时减一。代码实现def majority_element_third(nums): cand1 None cand2 None cnt1 0 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 [] n len(nums) for c in (cand1, cand2): if c is not None and sum(1 for x in nums if x c) * 3 n: res.append(c) return res这里有个小坑cand1 和 cand2 可能出现重复值要在最后用 set 去重。上面的写法如果数组里只有一种元素cand2 可能是 None最后统计时注意过滤。核心思想仍然是抵消两个候选者各自拥有一个计数器遇到不同时两个计数器同时消耗这和“两个不同元素抵消一个候选者的票数”在语义上是等价的。5.2 扩展到 n/k 的通用思路推广到 k 的情况需要维护 k-1 个候选者和计数器。当新元素与任何一个候选者相同对应的计数器加一如果有计数器为 0就加入新候选者否则所有计数器减一。复杂度是 O(nk)空间 O(k)。当 k 很小比如 2、3时非常高效但 k 很大时还不如哈希表。所以在工程里要先判断数据规模再决定用哪种算法不是越“高端”越好。5.3 流式数据上的应用摩尔投票法最迷人的应用场景是流式统计。想象一个系统不断接收用户点击事件你想知道当前窗口中是否存在某个占多数的用户。因为算法只需要保存候选者和计数所以每个事件处理都是 O(1)内存不变非常适合在实时计算管道里跑。但不是所有流式场景都能直接用。如果数据分布随时变化比如某个用户之前占多数、后来失去优势算法只能反映“从开始到现在”的整体趋势不能准确反映最近时间窗口的情况。如果你要的是滑动窗口内的多数元素需要配合窗口机制或衰减计数这个变体就被称作“带遗忘的摩尔投票”在推荐系统、异常检测里有不少应用。6. 摩尔投票法的应用场景和工程取舍6.1 适合用在什么地方分布式日志分析在多个节点上分别记录访问日志需要找出某种特定请求是否占了一半以上。每个节点可以独立跑一遍摩尔投票把候选者和计数汇聚到中心节点再做一次合并。硬件或嵌入式环境内存只有几个 KB数据却从传感器不停进来想要判断某个读数是否是主流读数摩尔投票几乎是唯一选择。数据库聚合运算某些数据库引擎在实现“统计值超过一半”的聚合算子时会采用类似摩尔投票的思路来减少中间结果大小。这些场景的共同特点是对空间极其敏感或者数据流不可回放。如果你能轻松把数据装进内存哈希表往往更直观、更容易维护没必要强行用它。6.2 不适合用在什么地方如果数据没有“严格多数元素”摩尔投票第一遍得到的结果没有意义必须再扫一遍。如果你需要所有出现次数超过 1% 的元素而不是超过 50%摩尔投票也不是好选择那应该用 Count-Min Sketch 或哈希表。另外摩尔投票对顺序不敏感但它不能告诉你“多数元素占比多少”。如果你需要精确的百分比仍然需要额外统计。6.3 与分治法的对比其实 Majority Element 问题也能用分治法做把数组分成两半分别找出左右两边的多数元素再合并。合并时比较两个候选者哪个出现次数更多。复杂度也是 O(n log n) 时间、O(log n) 递归栈空间不如摩尔投票的 O(n) 时间、O(1) 空间优雅。分治法比摩尔投票更容易理解适合作为教学引入但面试时如果遇到这个题摩尔投票基本是最优解。我见过不少人把分治法写出来然后面试官追加要求“能不能 O(1) 空间”才转而写摩尔投票。7. 我踩过的坑和一些需要反复强调的细节7.1 每次写之前都容易错的条件顺序摩尔投票虽然代码短逻辑顺序一旦错了结果就全乱。正确的顺序是先判断 count 0再判断是否等于 candidate最后才是抵消。如果你把顺序写成if num candidate: count 1 elif count 0: candidate num count 1 else: count - 1这样也能工作但候选者已经被设置过一次后遇到第一个元素且 count 为 0 时会进入num candidate分支吗如果 candidate 初始为 None不会但如果 candidate 初始为 0 且数组里第一个元素就是 0会出现误加。这就是为什么很多模板喜欢先把 candidate 初始化为第一个元素而不是用哨兵值。我建议记住官方模板的语义顺序先补位再累计再抵消。这样逻辑最清晰。7.2 不验证直接返回导致的错误我接过一个线上问题排查某个统计模块输出结果偶尔错误后来发现是数据流里并不保证存在严格多数元素但同事只做了第一遍摩尔投票就直接返回了候选者没有二次验证。结果在某些数据排列下候选者根本不是多数元素。所以只要你不能百分之百确认输入满足条件第二遍验证必须做。哪怕面试时题目说了“保证存在”我也建议你心里时刻有这一层意识因为面试官很可能紧接着就把条件改掉。7.3 关于“投票”这个名字的误导很多人以为摩尔投票法是“少数服从多数”“进行多次投票”其实它的本质是“抵消”。叫投票法是因为它看起来像一个候选者在收集选票但真正起决定性作用的是减票机制。理解了这个你才能自然推广到 n/3 和 k 的情况。我见过有人写博客把摩尔投票法描述成“每个元素投自己一票最后票数最多的胜出”这个描述是错了一半。如果真是简单投票你就需要一个哈希表计数。摩尔投票不一样它不是在对全局计数而是在做局部的成对抵消。7.4 数据元素不是整数时怎么办摩尔投票只依赖相等性比较不依赖大小比较所以理论上任何类型都可以只要你能判断两个元素是否相等。C 里自定义类型要重载JavaScript 里注意对象比较是引用比较如果你传入的是对象引用那引用地址不同的对象即使内容相同也会被当成不同元素。如果数据来自数据库元素是字符串也完全没问题。羊肉串、域名、用户 ID 都能当“元素”。但如果是浮点数注意 -0.0 和 0.0 在部分语言里相等但在某些语言里哈希值不同需要先统一归一化。8. 快速刷题时的思考路径总结最后分享一套我做这类题的思维模式帮你快速判断能不能用摩尔投票题目问的是“出现次数超过一半的元素”还是“占比最高的元素”前者可以用摩尔投票后者应该用哈希或堆。有没有限制空间复杂度 O(1)如果没限制哈希表最省心一旦限制摩尔投票的优先级立刻最高。输入数据能否自由遍历两遍能的话大胆用双扫描方案只能遍历一遍且数据流不可回放就必须在第一遍过程中记录足够信息此时摩尔投票的流式优势就体现出来了。是否要返回所有满足条件的元素如果是“超过 n/3”需要维护两个候选者如果是“超过 n/4”维护三个候选者。不要把公式记死记“k-1 个候选者”这个规律。算法本身只有十几行但背后的配对消除思想才是真正值钱的东西。我最初理解这个算法时一直纠结于“为什么换候选者不会丢掉真正的多数元素”后来把它完全当成“两两不同抵消”的模型所有疑问都消失了。你如果在看这一篇建议也亲手跑几个残缺的用例比如没有多数元素的数组、[1,1,2,2]、[3,3,3,1,2] 这种边界自己感受一下候选者变化的过程。我在实际工程里用到它最多的场景反而是某一天要排查“系统里哪个事件类型占了日志流的大头”当时数据根本落不了地全靠这个算法在内存里实时维护一个候选事件类型。那一刻才真正体会到教科书上看起来简单的算法有时候比那些复杂的分布式方案还管用。
阅读完成 · 觉得有帮助？
