多数元素四解法：摩尔投票O(1)空间与工程扩展

数组中出现次数超过一半的数字，这道题在面试题库里属于“老演员”了，但我在做代码评审和帮人看简历项目时发现，真正能把这道题讲透的人并不多。大部分人能背出摩尔投票的模板，却说不清为什么“超过一半”这个前提能让空间压到 O(1)，也说不出排序取中为什么天然正确，更谈不上把它迁移到“超过 n/3”“数据流求众数”“分布式统计”这类真实场景里。这篇文章就把这道题从题面拆解、方案选型、代码实现、边界坑位一直聊到泛化扩展，把四种主流解法的取舍逻辑摆开讲清楚。适合刚刷题不久、想把基础打牢的朋友，也适合已经工作几年、需要在工程里做频次统计和候选合并的同行。我会给出可直接复现的代码、手推的执行过程表，以及几条文档里不会写的实测心得。

1. 这道题到底在考什么：从题面条件说起

1.1 题面拆解与那几条容易被忽略的隐藏约束

先复述一遍题目：给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。看起来只有两句话，但里面藏了三个关键信息，值得逐条抠。

第一，“超过一半”是严格大于，不是大于等于。n=2 时，出现两次才算超过一半（2 > 1），出现一次不算。这个“严格大于”的措辞决定了：答案如果存在，一定是唯一的。因为两个数各自都超过 n/2，加起来就超过 n 了，与数组实际长度矛盾。唯一性这一点极其重要，它是后面所有“取巧”解法的合法性来源。

第二，“保证存在”这四个字决定了算法要不要做二次验证。面试题默认输入合法，可以在找到候选人后直接返回；但工程代码里我强烈建议保留验证环节，因为上游数据出错时，静默返回一个错值比抛异常更难排查。

第三，数组元素类型没被限定。如果是整数，可以玩位运算、可以排序；如果是字符串或对象，排序和哈希的代价完全不同。很多人在实现时默认 int，换成 long 或者 String 就出问题，这是我在评审时见得最多的一类疏忽。

提示：拿到题目先问三个问题——是否保证答案存在、元素是否可比较、是否允许修改原数组。这三问答完，方案基本就定了。

1.2 为什么“超过一半”这个条件如此值钱

如果题目改成“出现次数最多的数字”，那这题就是标准的众数问题，哈希计数是唯一稳妥的通用解，空间很难降到 O(1)。加上“超过一半”之后，问题性质发生了质变：候选集合被压缩到了一个，而且具备了“可抵消”的代数性质。

我习惯用一个生活化的类比来解释：假设一个班级里某个同学的人数超过全班一半，那么无论怎么两两配对（一个该同学配一个其他人），最后一定会剩下至少一个该同学。这个“配对抵消”的直觉，就是摩尔投票法的全部内核。反过来，如果条件只是“人数最多”，配完可能一个都不剩，你就没法判定谁是赢家。

从信息论角度看，超过一半意味着答案携带了超过 1 bit 的多数信息，可以用常数空间在线推断；而一般众数需要 Omega(n) 的空间才能精确求解。这个差别不是常数级别的优化，而是复杂度量级的差异，也是这道题能成为经典的根本原因。

2. 四条路线的选型对比：先想清楚再动手

2.1 路线一：哈希计数，最直白也最不容易翻车

拿到题的第一反应通常是开一个字典，遍历一遍累加频次，同时维护当前最大值，发现某个数计数超过 n/2 就直接返回。时间复杂度 O(n)，空间复杂度 O(n)，代码十行以内，逻辑无懈可击。

我个人的习惯是面试时先把这版写出来。原因很实际：它是保底方案，先拿到一个“能跑通”的版本，再去优化，面试官对你的评价会稳很多。上来就写摩尔投票，一旦边界写错，反而显得基本功不扎实。

但这版有它的真实短板。第一是空间，n 是一亿时，哈希表本身的内存占用和扩容抖动都会成为问题，尤其是 Java 的 HashMap，节点对象开销和负载因子 0.75 带来的冗余容量，实际内存可能是原始数据的五六倍。第二是哈希冲突，最坏情况下单次查询退化成链式遍历，虽然现代实现有红黑树兜底，但 O(n) 的均摊保证是有条件的。第三是它在分布式场景下不好合并，你得把整张表 shuffle 到一起才能汇总。

2.2 路线二：排序取中，一行代码背后的严谨证明

排序之后取下标 n/2 的元素，这是最短的解法。很多人会背“排序后中间那个就是答案”，但被追问“为什么”时答不上来。证明其实很干脆，用反证法：

假设答案 x 出现次数超过 n/2，排序后它占据了若干个连续位置 [L, R]，区间长度 R-L+1 > n/2。如果下标 n/2 不在这个区间里，那么 x 占据的位置要么全部落在 n/2 左侧（此时 R < n/2，即 R ≤ n/2 - 1，可容纳的位置数最多 n/2，与长度 > n/2 矛盾），要么全部落在右侧（同理矛盾）。所以 n/2 必然落在 [L, R] 内，取到的必定是 x。

代价是 O(n log n) 的时间和排序所需的辅助空间。对于基本类型数组，Java 的 Arrays.sort 用双轴快排，原地排序，额外空间 O(log n)；Python 的 sorted 用 Timsort，需要额外 O(n) 空间，这一点经常被忽略。还有一个隐形代价：它修改了原数组。如果调用方后续还要用原顺序，必须先拷贝，那一份 O(n) 的拷贝就把空间优势抹平了。

2.3 路线三：快速选择，把“排序”里的无用功砍掉

既然只需要第 n/2 位置的元素，那完全没必要把整个数组排好。快速选择（Quickselect）用一次 partition 把数组分成“小于基准”“等于基准”“大于基准”三段，判断第 n/2 位落在哪一段，只递归那一段。期望时间复杂度 O(n)，最坏 O(n²)。

最坏情况出现在基准选取极不均衡时，比如数组已经有序而你固定取第一个元素当基准。工程上的标准做法是随机化基准，或者用“三数取中”。我实测下来，随机化 pivot 在百万级数据上基本能稳定在期望复杂度附近，但要注意随机数生成本身的开销——如果数据量不大（几千以内），排序反而更快，因为常数因子小。

这里有个细节值得单独拎出来：如果你用普通的两分区 partition，遇到大量重复元素时性能会严重退化，因为等于基准的元素会全部堆在一边。处理这道题必须用三分区（荷兰国旗问题那套写法），把相等的元素聚到中间，遇到全相同的数组时一次 partition 就能直接命中。这个坑我踩过，普通分区在“一百万个相同数字”的用例上跑了十几秒。

2.4 路线四：摩尔投票，O(1) 空间的杀手锏

核心就两个变量：候选人 candidate 和计数器 count。遍历数组，count 为 0 时把当前元素设为候选人并将 count 置 1；否则若当前元素等于候选人则 count 加一，不等则 count 减一。遍历结束后 candidate 就是答案（前提是答案确实存在）。

时间和空间都是这道题的最优解，O(n) 时间、O(1) 空间、只遍历一次、不改原数组。它的价值不只是面试加分，在流式数据、内存受限的嵌入式环境、以及需要可合并统计的分布式场景里，这几乎是唯一可行的精确解法。

2.5 横向对比与选型建议

把四条路线的关键指标摊在表里，选型逻辑一目了然。

选型的经验判断是这样的：如果面试只给十分钟，先写哈希拿分，再说摩尔投票；如果数据量超过内存、或者是一条不能回放的数据流，直接上摩尔投票；如果数组本身已经有序或者接近有序，排序取中反而是最省事的；如果需求是“找第 k 大的同时顺便找众数”，快速选择一次 partition 能同时服务两个目标，这时候它的性价比最高。

3. 摩尔投票的完整实现与细节推演

3.1 抵消思想的生活化解释

我一般这么跟人讲：把所有元素想象成不同阵营的人，站在操场上。规则是每次抓两个人出来，如果来自不同阵营，两人同时离场；如果来自同一阵营，就攒着不放。因为某个阵营的人数超过总人数的一半，那么无论怎么抓，最后场上剩下的必然是这个阵营的人。

换成数组语言就是：candidate 记录当前“可能的赢家”，count 记录它还有多少“净剩余票数”。遇到同阵营的加一，遇到不同阵营的减一（相当于同归于尽）。count 归零意味着之前那批人被完全抵消了，此时把候选人换成当前元素重新开始计数。

这个思路之所以能成立，关键在于“抵消不会误伤赢家”：赢家的票数超过一半，即便每次抵消都拿掉一张赢家的票，它至少还能剩下（总票数 - 非赢家票数）> 0 张，永远不可能被彻底抵消干净。

3.2 为什么候选人必须做二次验证

这一点是区分“背模板”和“真懂”的分水岭。摩尔投票的第一阶段只能保证：如果存在超过一半的元素，那它一定是最终的 candidate。注意是“如果存在”。如果不存在，第一阶段照样会给你一个 candidate，只是它的真实频次不超过 n/2。

举个最简例子：[1, 2, 3]。过程是 candidate=1,count=1 → 遇到 2，抵消成 count=0 → 遇到 3，candidate=3,count=1。返回 3，但 3 只出现了一次。没有验证环节，这段代码就是错的。

所以工业级实现一定是两阶段：先选候选人，再统计该候选人的真实出现次数，与 n/2 比较，超过才返回，否则返回一个明确的“不存在”标记。多花一次 O(n) 遍历换来的正确性，非常划算。

注意：题目说“保证存在”就可以省验证，但一旦这个函数被复用到“不保证存在”的场景，省掉的验证就是埋雷。我自己的习惯是拆成两个函数，一个纯选候选，一个做验证，调用方自己组合。

3.3 多语言实现与写法细节

Python 版本，注意 count 变量名不要和列表的 count 方法混淆，我一般叫 votes：

def majority_element(nums): if not nums: return None candidate, votes = None, 0 for x in nums: if votes == 0: candidate, votes = x, 1 elif x == candidate: votes += 1 else: votes -= 1 # 二次验证，不假设输入合法 if nums.count(candidate) * 2 > len(nums): return candidate return None

Java 版本，这里有个小坑：如果数组元素是 Integer 而不是 int，千万不要用 == 比较，那比的是引用。要么转成 intValue 比较，要么用 equals：

public static Integer majorityElement(int[] nums) { if (nums == null || nums.length == 0) return null; int candidate = nums[0]; int votes = 0; for (int x : nums) { if (votes == 0) { candidate = x; votes = 1; } else if (x == candidate) { votes++; } else { votes--; } } int real = 0; for (int x : nums) { if (x == candidate) real++; } return real * 2 > nums.length ? candidate : null; }

Go 版本，返回 (值, 是否存在) 的双值风格更符合惯例：

func majorityElement(nums []int) (int, bool) { if len(nums) == 0 { return 0, false } candidate, votes := nums[0], 0 for _, x := range nums { if votes == 0 { candidate = x votes = 1 } else if x == candidate { votes++ } else { votes-- } } real := 0 for _, x := range nums { if x == candidate { real++ } } return candidate, real*2 > len(nums) }

三个版本的逻辑完全一致，差别只在语言习惯。我建议手写时统一用“votes 为 0 时重新立候选”这个结构，不要写成“先判断相等再判断归零”，后者在 count 归零的那一轮处理顺序上容易出错。

3.4 手推一遍执行过程

光看代码容易飘，拿一个具体数组走一遍，印象会深得多。以 [2, 2, 1, 3, 1, 2, 2] 为例，答案应该是 2（出现 4 次，超过 7/2 = 3.5）。

最终 candidate=2，验证阶段数一下确实出现 4 次，4*2=8 > 7，返回 2。这里能清楚看到第 3 到第 5 步那一段：原本领先的 2 被 1 和 3 逐步抵消掉，中途甚至一度把 1 顶上了候选位，但因为 2 的总量足够多，最后一轮又重新夺回候选身份。

这个模拟还展示了另一个要点：candidate 在过程中可能频繁变化，它只是“当前幸存者”，不是“最终答案”。只有遍历完整之后，幸存者才具备“若答案存在则必为它”的性质。

4. 边界条件与常见坑位实录

4.1 输入合法性：题目保证与工程现实的距离

题目说“保证存在”，但真实代码里我从来不这么假设。上游传个空数组、传个越界的长整型、传个含 null 的列表，都会让“保证”变成一句空话。我的固定做法是：入口处先做长度校验，空数组直接返回明确的空值；然后在选候选之后强制验证；最后把“不存在”和“输入为空”用不同返回值区分开，方便调用方定位问题。

用 Python 举例，返回 None 同时代表“空输入”和“不存在”是不合适的，因为调用方无法区分是数据没传进来还是数据本身有问题。我现在更倾向于抛一个自定义异常或者返回一个带状态的对象，虽然代码变长了，但排障时省的时间远多于写代码的时间。

还有一个容易被忽略的点：验证阶段的频次统计不要用count * 2 > n之外的变体，比如count > n // 2。后者在 n 为奇数时是等价的，但写成count >= n // 2就错了，会在 n=2、count=1 时误判为真。这类差一错误在代码评审里出现频率极高。

4.2 空数组、单元素、极值与负数

这几类用例我每次都会跑一遍，成本极低但抓 bug 很准。

• 空数组：长度为 0 时任何“取 n/2”的写法都会越界，排序取中方案必须单独处理。
• 单元素：n=1，唯一元素出现 1 次，1 > 0.5，应该返回它。摩尔投票天然支持，快速选择要注意 pivot 索引边界。
• 全相同：摩尔投票只会有一位候选人，count 一路加到 n，快；快速选择如果用两分区且基准选得不好，可能退化成 O(n²)，必须用三分区。
• 含负数：如果实现里用负数做标记位（比如把访问过的位置改为 -1），一遇到负数就崩。这是我见过的最典型的“只在正数用例上通过”的 bug。
• 极大值：Java 里用 Integer.MIN_VALUE 当哨兵时要小心，取反或取绝对值会溢出。用 long 或者用布尔标记数组更稳。

4.3 常见问题速查表

把我在实际调试中遇到的问题整理成表，遇到异常先对着查一遍。

5. 从一题到一类：超过 n/3 与数据流场景的扩展

5.1 超过 n/3 的两个候选人

把阈值从 1/2 降到 1/3，结论变成：最多只可能有两个元素的出现次数超过 n/3（三个都超过就超过 1 了）。摩尔投票也要相应扩展成“双候选双计数”。

规则是：先用两个变量 candidateA、candidateB 和对应的 votesA、votesB。遍历时如果当前元素等于 A 或 B，对应计数加一；如果 A 或 B 有空位（计数为 0），填入空位并置 1；两者都不为空且都不相等时，两个计数同时减一，表示三个不同元素一次性抵消。遍历结束后对两个候选人各自做一次真实频次统计，超过 n/3 的才输出。

这里有一个极易踩的坑：抵消时必须是“两者同时减一”，而不能只减其中一个。因为一次抵消消耗的是三个互不相同的元素，如果只减一个，抵消的基数就不对了，结论会崩。我第一次实现时就没注意，用一个 if-else 只减了一边，结果在一组精心构造的用例上翻车，调了半天才发现问题出在抵消的对称性上。

泛化到超过 n/k，就是维护 k-1 个候选人和 k-1 个计数，遇到不属于任何候选的元素时全体计数减一。时间 O(nk)，空间 O(k)。k 固定时是线性的；k 随 n 变化时，这个算法就退化了，那时该用哈希。

5.2 数据流与分布式场景下的可合并性

这是我认为这道题最有工程价值的延伸。摩尔投票的状态 (candidate, votes) 是可以合并的：给两段数据各自的统计结果，如果候选相同，票数相加；如果不同，票数相减，票数小的那方候选被淘汰，保留票数大的候选，票数为两者之差（相等则归零）。这个合并满足结合律，所以可以分块并行处理，再把各块结果两两归并。

举个实际的做法：一亿条日志分散在一百个分片上，每个分片本地跑一遍摩尔投票得到 (candidate, votes)，然后把这最多一百个二元组汇总到一个节点，反复做两两合并，最后得到全局候选，再回到各分片统计该候选的真实总数，判断是否超过总数一半。整个过程的中间数据量只有 O(分片数)，完全不用把原始数据搬来搬去。

具体合并函数的写法大致是这样：

def merge(state_a, state_b): cand_a, votes_a = state_a cand_b, votes_b = state_b if votes_a == 0: return state_b if votes_b == 0: return state_a if cand_a == cand_b: return (cand_a, votes_a + votes_b) if votes_a > votes_b: return (cand_a, votes_a - votes_b) elif votes_a < votes_b: return (cand_b, votes_b - votes_a) else: return (None, 0)

这个形式的好处是天然适合归约运算，写 map-reduce 或者用流式聚合都很顺。但要记住合并的仍然只是“候选”，最终判断是否真的超过一半，还是得回到全量数据上统计一次，别把候选当结论直接用了。

5.3 几个常见的变体题型

除了原题，同源的变体我整理了几个，练习时可以串起来做，效果比刷一堆不相干的题好。

第一类是“找出所有出现次数超过 n/3 的元素”，就是上面双候选的版本，输出可能为空、一个或两个。第二类是“判断某个给定的数 x 是否出现次数超过一半”，这个最简单，一遍遍历计数即可，O(n) 时间 O(1) 空间，连投票都不用。第三类是“数据流中随时查询众数”，如果不保证超过一半，那就得用堆或者平衡树维护频次，做不到 O(1) 空间。第四类是“找出现次数恰好为一半的元素”，注意此时不可能唯一，且摩尔投票会失效，得用哈希。

还有一个变体挺有意思：数组里只有一个数出现奇数次，其他都出现偶数次，求这个数。用异或一遍扫过就行。它和摩尔投票的心法相通——都是靠“相同抵消”的性质把非目标元素吃掉，区别在于异或利用的是位级的自反性，摩尔投票利用的是计数上的相消性。把这两题放一起看，对“抵消类算法”会有整体的感觉。

6. 我在实际使用中的几点体会

最后说几条纯个人经验，都是踩过之后才记住的。

第一条，别急着优化空间。我在早期做类似统计需求时，一上来就想用摩尔投票省内存，结果因为数据源不保证“超过一半”，验证阶段屡屡失败，反而多写了一堆兜底逻辑。后来学乖了：先看数据特征，确认阈值条件成立再用 O(1) 方案，不成立就老老实实上哈希。算法选型的第一原则是匹配问题约束，不是追复杂度最优。

第二条，验证环节千万别省。不管是自己写还是评审别人的代码，只要看到“直接返回 candidate”而没有任何频次校验，我就会打回去。多一次遍历的代价是 O(n)，而错一次的结果可能是整份报表全错，这个账很好算。

第三条，重复元素多的数据要专门测。我吃过一次亏，快速选择在随机数据上跑得飞快，上线后遇到大量重复值的真实数据，耗时涨了将近十倍。从那以后我的测试用例里固定加一组长全相同的数组，和三组随机数组一起跑。

第四条，如果只是找众数而不要求超过一半，别硬套这道题的解法。摩尔投票在这种场景下给你的候选人是不可靠的，二次验证一定失败，代码看起来“有时对有时错”，最难排查。老老实实用哈希计数，简单直接，日志里把最大频次记下来，后面做数据质量分析还用得上。

调试这块再分享一个小技巧：把摩尔投票的每一步状态打印成一行，格式是“下标、元素、候选、票数、动作”，跑一组十来个元素的数组，肉眼扫一遍就能看出逻辑是否符合预期。这个方法比断点单步快得多，尤其是在你不熟悉某门语言边界行为的时候。