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

数组中出现次数超过一半的数字这道题在面试题库里属于“老演员”了但我在做代码评审和帮人看简历项目时发现真正能把这道题讲透的人并不多。大部分人能背出摩尔投票的模板却说不清为什么“超过一半”这个前提能让空间压到 O(1)也说不出排序取中为什么天然正确更谈不上把它迁移到“超过 n/3”“数据流求众数”“分布式统计”这类真实场景里。这篇文章就把这道题从题面拆解、方案选型、代码实现、边界坑位一直聊到泛化扩展把四种主流解法的取舍逻辑摆开讲清楚。适合刚刷题不久、想把基础打牢的朋友也适合已经工作几年、需要在工程里做频次统计和候选合并的同行。我会给出可直接复现的代码、手推的执行过程表以及几条文档里不会写的实测心得。1. 这道题到底在考什么从题面条件说起1.1 题面拆解与那几条容易被忽略的隐藏约束先复述一遍题目给一个长度为 n 的数组数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。看起来只有两句话但里面藏了三个关键信息值得逐条抠。第一“超过一半”是严格大于不是大于等于。n2 时出现两次才算超过一半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-L1 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 横向对比与选型建议把四条路线的关键指标摊在表里选型逻辑一目了然。方案时间复杂度空间复杂度是否改原数组适用场景主要风险哈希计数O(n) 均摊O(n)否通用、需同时拿到频次内存占用大、哈希冲突排序取中O(n log n)O(log n)~O(n)是数组已部分有序、代码要短大数组慢、破坏原数据快速选择期望 O(n)O(1)~O(log n)是只需求第 k 位、数据可打乱最坏退化、重复元素多摩尔投票O(n)O(1)否流式、内存受限、分布式必须二次验证、只出一个答案选型的经验判断是这样的如果面试只给十分钟先写哈希拿分再说摩尔投票如果数据量超过内存、或者是一条不能回放的数据流直接上摩尔投票如果数组本身已经有序或者接近有序排序取中反而是最省事的如果需求是“找第 k 大的同时顺便找众数”快速选择一次 partition 能同时服务两个目标这时候它的性价比最高。3. 摩尔投票的完整实现与细节推演3.1 抵消思想的生活化解释我一般这么跟人讲把所有元素想象成不同阵营的人站在操场上。规则是每次抓两个人出来如果来自不同阵营两人同时离场如果来自同一阵营就攒着不放。因为某个阵营的人数超过总人数的一半那么无论怎么抓最后场上剩下的必然是这个阵营的人。换成数组语言就是candidate 记录当前“可能的赢家”count 记录它还有多少“净剩余票数”。遇到同阵营的加一遇到不同阵营的减一相当于同归于尽。count 归零意味着之前那批人被完全抵消了此时把候选人换成当前元素重新开始计数。这个思路之所以能成立关键在于“抵消不会误伤赢家”赢家的票数超过一半即便每次抵消都拿掉一张赢家的票它至少还能剩下总票数 - 非赢家票数 0 张永远不可能被彻底抵消干净。3.2 为什么候选人必须做二次验证这一点是区分“背模板”和“真懂”的分水岭。摩尔投票的第一阶段只能保证如果存在超过一半的元素那它一定是最终的 candidate。注意是“如果存在”。如果不存在第一阶段照样会给你一个 candidate只是它的真实频次不超过 n/2。举个最简例子[1, 2, 3]。过程是 candidate1,count1 → 遇到 2抵消成 count0 → 遇到 3candidate3,count1。返回 3但 3 只出现了一次。没有验证环节这段代码就是错的。所以工业级实现一定是两阶段先选候选人再统计该候选人的真实出现次数与 n/2 比较超过才返回否则返回一个明确的“不存在”标记。多花一次 O(n) 遍历换来的正确性非常划算。注意题目说“保证存在”就可以省验证但一旦这个函数被复用到“不保证存在”的场景省掉的验证就是埋雷。我自己的习惯是拆成两个函数一个纯选候选一个做验证调用方自己组合。3.3 多语言实现与写法细节Python 版本注意 count 变量名不要和列表的 count 方法混淆我一般叫 votesdef 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 NoneJava 版本这里有个小坑如果数组元素是 Integer 而不是 int千万不要用 比较那比的是引用。要么转成 intValue 比较要么用 equalspublic 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。下标当前元素操作candidatevotes02votes0立候选2112相等加一2221不等减一2133不等减一2041votes0立候选1152不等减一1062votes0立候选21最终 candidate2验证阶段数一下确实出现 4 次4*28 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就错了会在 n2、count1 时误判为真。这类差一错误在代码评审里出现频率极高。4.2 空数组、单元素、极值与负数这几类用例我每次都会跑一遍成本极低但抓 bug 很准。空数组长度为 0 时任何“取 n/2”的写法都会越界排序取中方案必须单独处理。单元素n1唯一元素出现 1 次1 0.5应该返回它。摩尔投票天然支持快速选择要注意 pivot 索引边界。全相同摩尔投票只会有一位候选人count 一路加到 n快快速选择如果用两分区且基准选得不好可能退化成 O(n²)必须用三分区。含负数如果实现里用负数做标记位比如把访问过的位置改为 -1一遇到负数就崩。这是我见过的最典型的“只在正数用例上通过”的 bug。极大值Java 里用 Integer.MIN_VALUE 当哨兵时要小心取反或取绝对值会溢出。用 long 或者用布尔标记数组更稳。4.3 常见问题速查表把我在实际调试中遇到的问题整理成表遇到异常先对着查一遍。现象可能原因排查方向处理办法返回了一个只出现 1 次的数缺少二次验证打印 candidate 真实频次补上验证阶段排序后取中结果不对取了下标 n/2-1 或者 n/21检查取整方向统一用 n//2注意语言整除语义快速选择死循环partition 边界写错pivot 未移动打印每次 partition 的区间三分区并确保区间收缩全相同数组超时两分区退化统计等于 pivot 的元素数量改用荷兰国旗三分区大数据量内存爆掉用了哈希表或排序拷贝看峰值内存换摩尔投票或分块处理Java 里结果偶尔错乱Integer 用 比较检查是否有自动装箱用 intValue 或 equals 比较多线程下结果不稳定共享 candidate 和 votes 未同步加日志看竞态每线程独立统计再合并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)而错一次的结果可能是整份报表全错这个账很好算。第三条重复元素多的数据要专门测。我吃过一次亏快速选择在随机数据上跑得飞快上线后遇到大量重复值的真实数据耗时涨了将近十倍。从那以后我的测试用例里固定加一组长全相同的数组和三组随机数组一起跑。第四条如果只是找众数而不要求超过一半别硬套这道题的解法。摩尔投票在这种场景下给你的候选人是不可靠的二次验证一定失败代码看起来“有时对有时错”最难排查。老老实实用哈希计数简单直接日志里把最大频次记下来后面做数据质量分析还用得上。调试这块再分享一个小技巧把摩尔投票的每一步状态打印成一行格式是“下标、元素、候选、票数、动作”跑一组十来个元素的数组肉眼扫一遍就能看出逻辑是否符合预期。这个方法比断点单步快得多尤其是在你不熟悉某门语言边界行为的时候。