企业官网建设流程全解析

摩尔投票法（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。规则只有三条：

1. 如果 count 为 0，说明当前擂主已经死光，把新看到的元素设为 candidate，count 设为 1。
2. 如果新元素和 candidate 相同，count 加 1，相当于同阵营的人加入。
3. 如果新元素和 candidate 不同，count 减 1，相当于两个不同阵营的人同归于尽。

听起来像小孩玩“打架”游戏，但它的正确性很硬。用数组[2, 2, 1, 1, 1, 2, 2]走一遍，立刻能看到效果。

最终 stopping 在 candidate = 2，而 2 在这个数组中恰好出现了 4 次，超过 7 的一半。整个过程只扫了一遍，没有额外容器，非常干净。

不过这里必须先打个预防针：最后得到的 candidate 只是一个“候选人”，不代表它一定就是众数。如果数组本身不保证存在超过一半的元素，最后活下来的可能是“矮子里拔将军”。为什么需要第二步验证、怎么验证，我在第 3 章专门讲。

2. 算法完全拆解：从原理到数学直觉

2.1 两个变量怎么完成“全局占比判断”

很多人第一次看到 count 这个变量时，会觉得它只是个简单计数器。其实它的真正含义是：当前 candidate 相对其他所有元素的“净优势人数”。

具体来说，在遍历过程的任意时刻，可以这样理解当前状态：前面已经处理过的所有元素中，由于持续的“不同元素配对抵消”，剩下了一批未被抵消的元素。这批元素一定全是同一个值，也就是当前的 candidate；count 就是这批剩余元素的数量。一旦遇到一个新元素，它要么加入这批剩余元素（相同值），要么与这批剩余元素中的某一个抵消（不同值）。

举个例子，数组[2, 2, 1, 1]处理完前四个元素后，2 和 1 各有两个，两两抵消，剩余元素为 0，count 回到 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(vector<int>& 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 先成为 candidate，2 抵消它，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 = 1，candidate = 7，验证阶段 7 出现 1 次，大于 0.5，返回 7。
• 全相同元素：[5, 5, 5, 5]，candidate 从头到尾是 5，count 一直累加到 4，验证通过。
• 交替抵消：[1, 2, 1, 2]，没有元素过半。算法最终 candidate 可能是 2，验证阶段发现它只出现 2 次，不大于 n/2，返回 -1。

另外，如果语言是 Python，candidate 初始值用 None 时，要小心数组里真的包含 None 值。更稳妥的做法是先用一个哨兵标记“空位”，或者只处理类型明确的数值数组。C++/Java 里可以设置候选为数组首元素，count 初始为 0，这样也能避免“谁都不认识”的初始态问题。这些小细节不会影响算法本身，但直接影响代码健壮性。

4. 复杂度对比与进阶变体

4.1 时间 O(n)、空间 O(1) 到底意味着什么

把摩尔投票法和其它思路放在一张表里，差距一目了然。

“O(1) 空间”在海量数据场景里是决定性的优势。数据量达到十亿级别时，O(n) 的空间意味着要上百 GB 内存，而 O(1) 就是几十字节。单遍扫描也很重要：很多数据源是磁带、网络包、日志文件，只能顺序读取一次，不能像数组那样随机访问。所以摩尔投票法天然适配“流式环境”，这也是它能从算法题库走进真实系统的原因。

4.2 从找 n/2 延伸到找 n/3：两个候选人

如果题目改成“找出所有出现次数超过 n/3 的元素”，摩尔投票法还能用吗？能，而且思路是同一个，只是从“两个不同元素互相抵消”升级成“三个不同元素一起抵消”。

先想清楚一个前提：超过 n/3 的元素最多只能有两个。因为如果有三个元素都超过 n/3，它们总出现次数就会超过 n，显然不可能。所以算法只需要维护两个候选人和两个计数器。遍历数组时，按顺序执行以下规则：

1. 如果当前元素等于 candidate1，则 count1 加 1。
2. 如果当前元素等于 candidate2，则 count2 加 1。
3. 如果 count1 为 0，把当前元素设为 candidate1，count1 = 1。
4. 如果 count2 为 0，把当前元素设为 candidate2，count2 = 1。
5. 否则，说明当前元素和两个候选人都不同，触发一次“三方抵消”：count1 减 1，count2 减 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 个 x，B 段还剩 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 面试/笔试中容易被卡住的三道关

我把平时见到的经典追问整理成几个速查问题，每个问题的答案都能反映对算法的理解深度。

面试官如果追问“为什么 count 减到 0 后，前面的数据就像没发生过一样”，最好的回答方式是讲清楚配对抵消：每一步抵消操作都是把两个不同的元素从“待统计池”里删除，而这种删除不会改变某个阵营是否过半的性质。如果有一个阵营真的过半，它在任意一轮抵消中被消耗的速度不可能超过它增长的速度。

6.2 手写代码时的四个经典错误

看别人代码时感觉简单，自己动手写就容易翻车。以下四个坑我基本每次帮人 review 都能碰到。

这四条里，第一、四条最隐蔽，因为它们不会导致语法错误，而是让结果在某些用例上悄悄翻车。建议写完代码后，至少跑这三组用例：[]（空）、[2, 2, 1, 1, 1, 2, 2]（有众数）、[1, 2, 3]（无众数）。能一次性通过，基本就稳了。

6.3 写在最后：一点个人的实操体会

我最初接触到摩尔投票法时，第一反应是“这也能行？”后来在日志分析里真正用了一次，才发现它的价值不在“面试背题”，而在“把复杂度从不可能降到可能”。工程上遇到“超大流 + 找主流”的问题，我现在的第一反应已经不是 HashMap 了，而是先问自己：要不要用抵消思想？候选值能不能接受二次验证？如果能，摩尔投票法往往就是最优解。

有几条经验是踩过坑之后才悟出来的。一是千万别省验证阶段；写代码时多写一个循环不丢人，丢人的是线上返回了一个错误的“众数”。二是解释算法时一定要从“配对抵消”说起，不要上来就背代码；只有理解了抵消的语义，遇到变体题才不会慌。三是扩展思路比孤立记忆重要；从 n/2 走到 n/3、n/k，其实就是同一个思想在不同规模下的延伸。如果你哪天在流式场景里需要找 top-k 高频项，会发现摩尔投票法那套“固定数量候选人 + 多路抵消”的思路，居然还能继续发光。