摩尔投票法详解：多数元素、O(1)空间与n/k推广

标题里那串重复的JZJZJZ前缀多半是从题单编号里复制粘贴时带出来的脏字符不影响题目本身——剥掉它剩下的就是一句非常经典的描述数组中出现次数超过一半的数字。这道题在算法面试里的地位有点特殊它看着简单谁都能写出一个哈希表版本交差但它又足够深面试官能顺着它一路追问到如果不保证答案存在怎么办如果改成超过三分之一呢能不能只用两个变量。很多人第一次做的时候用哈希表过了第二次被人问空间能不能 O(1)就开始冒汗第三次被要求讲清楚摩尔投票法为什么正确时只能含糊地说一句因为超过一半所以抵消不完。我把这道题前前后后折腾过好几轮从最初死记硬背那六行代码到后来能把它背后的抵消模型、证明思路、推广形式一条线讲清楚。这篇就按我自己的理解顺序来拆先说清题目里那几个容易被跳过的限定条件再把哈希、排序、快速选择这三种能过题的写法摆出来讲代价然后重点把摩尔投票法从直觉到证明到代码轨迹完整走一遍最后聊边界坑、面试追问链和 n/k 的推广。不管你是刚刷到这题还是已经背下答案但心里没底应该都能捞到点东西。1. 超过一半这四个字里藏着的三个限定条件1.1 题面还原从一个九元素数组说起先把题面完整摊开。给定一个长度为 n 的数组数组里有一个数字出现的次数严格超过数组长度的一半请找出这个数字。举个子{1, 2, 3, 2, 2, 2, 5, 4, 2}长度是 9数字 2 出现了 5 次5 4.5所以答案是 2。这段描述里有三个词必须抠出来单独看它们决定了你代码的边界写在哪。第一个是严格超过。n 9 的时候超过一半意味着至少 5 次n 8 的时候超过一半意味着至少 5 次而不是 4 次。换句话说门槛是floor(n/2) 1不是n/2。这个细节在做推广题的时候特别要命——如果题目说出现次数不少于一半那 n 8 时 4 次也算问题的性质就变了摩尔投票的证明前提直接崩掉。第二个是一个数字。题目默认这样的数字最多只有一个。这个结论很容易验证假设有两个数字都出现了超过 n/2 次那它们的出现次数之和就超过 n超过了数组总长度矛盾。所以答案唯一你不需要考虑返回多个结果的情况。第三个是出现次数超过一半这个条件本身是一个极强的先验信息。它意味着目标数字占据了数组的绝对多数任何试图稀释它的操作都不足以把它彻底冲掉。后面所有巧妙的解法本质上都是在利用这个先验信息而不是真的去统计每个数字出现了多少次。很多人刷这题时只盯着找出来这个动作忽略了条件本身携带的信息量结果就是条件反射地开一个 HashMap。能过但等于把题目送的最大的礼给扔了。1.2 为什么面试官偏爱这道题我后来想明白了一件事这道题之所以高频不是因为它难而是因为它分层极其清晰。同一道题不同水平的人能给出的答案差距非常大而且每一层都能继续往下问。最外层是哈希计数考的是你能不能把问题转化成计数问题这是基本功写不出来说明代码量还不够。往下一层是排序取中位考的是你能不能用数学性质绕过统计这一步开始有思考含量了。再往下一层是摩尔投票考的是你能不能在 O(1) 空间里完成并且讲清楚为什么。而真正拉开差距的是第四层当题目不保证答案存在时你的代码还对不对。我见过太多人背下了摩尔投票的六行代码但被问到如果数组里没有超过一半的数你的函数返回什么时直接卡住。因为那六行代码在没有答案的情况下会返回一个幸存者而这个幸存者根本不是答案代码却不会报错——这是典型的静默错误比崩溃更危险。所以这道题实际上是一个探针能探出三件事你的代码基本功、你对算法正确性证明的敏感度、以及你有没有验证结果这个工程习惯。最后一点在真实项目里比前两点加起来都重要面试官心里很清楚。1.3 先把不保证存在这个分支想清楚原始版本的题目是保证答案存在的有些版本还会额外约定如果不存在则返回 0。这两个约定对应两种完全不同的代码结构你在动手之前必须先确认是哪一种。如果是保证存在那摩尔投票一遍扫完直接返回候选值就行不需要复核代码最短。如果是不保证存在那必须在最后补一次遍历统计候选值的真实出现次数超过 n/2 才返回它否则返回约定的失败值通常是 0 或者 -1。这里有个非常容易被忽略的坑失败值不能用 0 当 Sentinel哨兵。因为 0 本身完全可能是一个合法答案比如{0, 0, 1}答案是 0如果你把没找到也编码成 0调用方根本分不清是找到了 0 还是压根没找到。正确做法是返回一个额外的布尔标志或者返回一个可选类型Optional / null / 包装类或者按题目约定返回一个数组里不可能出现的值——但最后这条在通用场景下不成立因为数组元素范围是任意的。我个人的习惯是函数签名上直接返回一个可能为 null 的包装类型或者返回一个包含found标志的结构。代码多几行但调用方不会误判。这个小决定在刷题时看着无所谓在真实业务里能省掉一次线上排查。2. 哈希、排序、快速选择能过题的三种常规打法与它们的真实代价2.1 哈希计数最容易写对的兜底方案哈希表的思路没有任何弯弯绕遍历数组用哈希表记录每个数字出现的次数一旦某个数字的计数超过 n/2立刻返回。public int majorityByHash(int[] nums) { if (nums null || nums.length 0) return -1; int half nums.length / 2; MapInteger, Integer cnt new HashMap(); for (int x : nums) { int c cnt.getOrDefault(x, 0) 1; if (c half) return x; // 提前返回不必扫完 cnt.put(x, c); } return -1; // 不存在 }时间 O(n)空间 O(n)。这段代码我建议每个人都手写一遍因为它是对照组后面所有优化的价值都要拿它来当基准衡量。你写摩尔投票的时候如果心里没这个基准容易产生我用了高级算法的自我感动实际上在 n 只有几十的场景下哈希表版本更快因为常数小、缓存友好、没有分支预测失败。这里有两个实操细节值得说。第一是提前返回不要在遍历结束后再去找最大值边遍历边判断平均能省掉一半的遍历。第二是getOrDefault的使用很多人习惯写if (map.containsKey(x))再取值等于查了两次哈希白白多一次寻址。哈希版本真正的短板不在时间而在空间。n 达到千万级别时一个HashMapInteger, Integer的内存开销极其夸张——Java 里每个 Entry 对象头、指针、装箱后的 Integer 对象加起来能到 48 字节以上一千万条就是几百兆。这就是为什么面试官会问空间能不能优化他问的不是理论复杂度好看不好看而是这个数据结构在生产环境里会不会把内存吃光。2.2 排序取中位三行代码背后的位置论证排序版本的代码短到有点不讲道理def majority_by_sort(nums): if not nums: return -1 nums.sort() return nums[len(nums) // 2]时间 O(n log n)空间取决于排序实现Python 的 Timsort 需要 O(n) 辅助空间原地快排是 O(log n) 栈空间。它比哈希慢但它的空间开销通常更小而且在很多语言的标准库排序对近乎有序的数据有优化实际跑起来未必慢多少。关键在于为什么下标 n/2 的位置一定是答案。这个结论不是玄学可以严格论证。设答案数字为 x它一共出现了 k 次且 k n/2。排序之后所有 x 挤在一起形成一个连续区间[p, pk-1]其中 p 是第一个 x 的下标。我要证明p ≤ n/2 ≤ pk-1也就是中位下标落在这个区间内。先证左半边如果p n/2那么从下标 p 到 n-1 一共只有n - p n - n/2 n/2个位置但这里要放下 k 个 x而 k n/2位置不够矛盾。所以p ≤ n/2。再证右半边如果p k - 1 n/2也就是p k ≤ n/2。那么区间[0, pk-1]只有pk ≤ n/2个位置却要装下这 k 个 x 以及排在他们前面的 p 个非 x 元素一共pk个元素刚好占满。剩下的n - (pk) ≥ n/2个位置全部是其他数字——这没问题但注意 k 个 x 全在这个长度不超过 n/2 的前缀里而 k n/2一个长度 ≤ n/2 的区间装不下 k n/2 个元素矛盾。所以pk-1 ≥ n/2。两边一夹n/2必然落在 x 占据的连续区间内。证明完毕。这个结论还有一个更直观的说法如果把数组排序后从中间切开任何出现次数超过一半的元素都必然跨越中点。因为它的势力范围太长了无论它从哪个位置开始都盖不住也躲不开中间那条线。这个几何直觉比公式好记。顺带说一句取下标是n // 2还是(n-1) // 2其实都对因为两个下标都在区间内。整数除法下n//2在 n 为偶数时取到偏右的那个中点无妨。2.3 快速选择 partition平均线性但会退化的选择既然只需要中位数那完整排序就是浪费——快排的 partition 过程每轮都能确定一个元素的最终位置我们只要盯住下标 n/2 那一路走下去就行另一侧完全不用管。这就是快速选择Quickselect平均时间复杂度 O(n)。public int majorityByQuickSelect(int[] nums) { int target nums.length / 2; int lo 0, hi nums.length - 1; while (lo hi) { int p partition(nums, lo, hi); if (p target) return nums[p]; else if (p target) lo p 1; else hi p - 1; } return nums[target]; } // 以 nums[hi] 为枢轴返回其最终下标 private int partition(int[] a, int lo, int hi) { int pivot a[hi]; int i lo; for (int j lo; j hi; j) { if (a[j] pivot) { int t a[i]; a[i] a[j]; a[j] t; i; } } int t a[i]; a[i] a[hi]; a[hi] t; return i; }平均 O(n)最坏 O(n²)。最坏情况什么时候出现当每次选中的枢轴都是当前区间的最小值或最大值时区间只缩小一个元素退化成 O(n²)。而这在已经有序的数组上恰好会发生——如果你固定取末尾元素当枢轴输入一个升序数组每轮 partition 都只能切掉一个元素。这个退化不是理论上的杞人忧天。真实数据里有序或近乎有序的数组非常常见比如按时间戳采集的 ID 序列、按主键导出的数据所以工程上要用快速选择必须做随机化枢轴或者三数取中。随机化只要一行int r lo new Random().nextInt(hi - lo 1); int t a[r]; a[r] a[hi]; a[hi] t;代价是引入了随机数生成的开销以及理论上仍然存在极小概率退化。所以快速选择这个方案我的态度是面试时可以提作为展示你理解 partition 的加分项实际项目里除非数据量真的很大且内存吃紧否则没必要上。它的代码复杂度、常数开销、最坏情况风险加起来并不比排序 取中位划算而后者一行就写完了。3. 摩尔投票法把两两抵消这件事拆到骨头3.1 为什么抵消这个直觉是对的前面三种解法要么花空间要么花时间。摩尔投票法的漂亮之处在于它同时做到 O(n) 时间和 O(1) 空间而且代码只有六行。但它的不讲道理程度也最高——第一次看到的人普遍的反应是这也行理解它的钥匙是一个物理模型把数组里的元素想象成不同阵营的人每次让两个不同阵营的人互相抵消掉。抵消这个动作有个关键性质它不会改变是否存在绝对多数这个事实。为什么假设某个阵营 x 占了超过一半的人数。每次抵消拿走两个人最多只有一个人来自 x 阵营因为要求两人阵营不同。那么 x 阵营的人数最多减少 1而总人数也减少 2。设 x 原来有 k 人总人数 nk n/2。抵消 t 次之后x 还剩k - t人总人数剩n - 2t。要保证 x 仍然是多数k - t (n - 2t) / 2等价于k - t n/2 - t等价于k n/2。看t 被消掉了。只要初始条件是多数无论抵消多少次它永远是多数。这就是整个算法成立的根基——抵消操作保持多数性不变。那要抵消多少次呢最多把非 x 的元素全部消完也就是 n - k 次。消完之后x 至少还剩k - (n-k) 2k - n个。因为 k n/2所以2k - n 0至少剩一个。所以最后活下来的阵营必定是 x。这个推理链条比代码本身重要得多。很多人背下代码后过两周就忘但如果记住了抵消不改变多数性这一句代码能自己推出来。3.2 六行代码与一趟完整的执行轨迹public int majorityElement(int[] 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; }这段代码的语义是candidate记录当前暂时领先的阵营count记录这个阵营尚未被抵消掉的人数。当count归零说明之前所有的人两两抵消干净了从下一个元素开始重开一局。拿{1, 2, 3, 2, 2, 2, 5, 4, 2}走一遍步骤当前元素candidatecount说明1111初始化站队 12210阵营不同抵消3331count 归零后重新站队4230阵营不同抵消5221重新站队6222同阵营加票7521抵消一对8420抵消干净9221重新站队最终candidate 2正确。注意第 3 步和第 4 步这段3 进来占了位置然后被 2 抵消掉第 5 步 2 重新站队。这一段其实就是把中间这段互不相同的元素两两消掉了。前面的 1 和 2 抵消、3 和 2 抵消一共消了两对。抵消完之后 2 还剩 3 个仍然是绝对多数。这个轨迹也能看出一个反直觉的点过程中的 candidate 完全可能是错误答案。第 1 到第 4 步candidate 依次是 1、1、3、3全都不是最终答案。所以你不能在过程中看到 count 冲高就下结论必须扫完整个数组。这一点和边遍历边返回的哈希版本形成了鲜明对比。3.3 严格证明为什么剩下的候选一定是它上面那段直觉推理写成正式形式是这样设数组长度 n目标数字 x 出现 k 次k n/2。把整个遍历过程看成一系列抵消操作的序列。每一次抵消我们从当前未抵消的元素中移除两个不同的元素。引理设某个时刻未抵消的元素集合为 S其中 x 出现k次。每次抵消后k最多减少 1而|S|减少 2。因此k - |S|/2这个量单调不减严格说如果被消掉的一对里有 x则k - |S|/2保持(k-1) - (|S|-2)/2 k - |S|/2 1 - 1不变如果不含 x则变为k - (|S|-2)/2 k - |S|/2 1增加 1。初始时k - n/2 0所以整个过程k - |S|/2 0恒成立即k |S|/2。当遍历结束时S 中剩下的元素必然全部相同——因为只要还剩两个不同的元素算法就会继续抵消。设剩下的元素是 y共 m 个|S| mk是 x 在 S 中的个数。由于 S 中只有 y如果y ≠ x则k 0与k m/2 ≥ 0矛盾。所以y x。这个证明里唯一用到的假设就是k n/2也就是严格超过一半。如果只是等于一半初始时k - n/2 0边界情况就可能翻转算法会失效。举个具体的反例{1, 2}1 和 2 各一次刚好一半摩尔投票最后返回 2但 2 并不是超过一半的答案因为它压根不存在这样的答案。这就是为什么题目必须写超过。还有一个细节算法最后剩下的count值不一定是 x 的真实出现次数它可能只是没被抵消掉的部分。比如{2, 2, 2, 1, 1}扫完后candidate 2, count 1但 2 实际出现了 3 次。所以绝对不要用最后的 count 当作答案的出现次数这是一个非常常见的使用错误。3.4 不保证答案存在时那趟必不可少的复核前面说了如果题目不保证答案存在六行代码会给你一个幸存者但这个幸存者可能是任意值。举几个例子{1, 2, 3}→ 返回 3但没有任何数字超过 1.5 次{1, 2, 1, 2, 3}→ candidate 依次变化最后返回 3同样无效空数组 → 返回初始化的 candidate可能是任意残留值修复方式就是补一趟计数public int majorityWithVerify(int[] nums) { if (nums null || nums.length 0) return -1; int candidate nums[0], count 0; for (int x : nums) { if (count 0) { candidate x; count 1; } else if (x candidate) count; else count--; } // 复核候选者的真实票数 int real 0; for (int x : nums) if (x candidate) real; return real nums.length / 2 ? candidate : -1; }多这一趟遍历时间复杂度仍是 O(n)空间仍是 O(1)代价可以忽略。但从工程角度这一趟遍历绝对不能省因为它的作用是把算法输出变成经过验证的结论。我在实际写业务代码时有个类似的习惯任何基于某种假设才有意义的计算结果都要在返回之前用最朴素的方式验证一遍。摩尔投票的复核就是这种模式的一个教科书级例子——假设是存在多数元素验证方式是数一遍。这个思路可以迁移到很多场景比如缓存一致性校验、索引与实际数据行数比对等等。算法题里养成的这种习惯最后会变成代码里的防御性设计。注意复核版本里candidate的初始化改成了nums[0]并且前面加了空数组判断。这是为了在 n 1 时也能正确工作{5}扫一遍 candidate 是 5复核 real 1 0返回 5。如果还用candidate 0初始化虽然结果也对但语义上是脏的。4. 边界与面试追问那些把人问懵的细节4.1 空数组、单元素与负数边界条件这块我按踩坑频率排序讲。空数组是第一位的。null 和length 0是两种不同情况严谨的写法要分别处理。很多题解直接假设输入非空因为题目有保证存在的前提——空数组里显然不可能有超过一半的数。但在真实调用链里上游传个空数组过来太常见了函数直接抛ArrayIndexOutOfBoundsException或者NullPointerException是很难看的。统一在入口处判掉返回约定的失败值。单元素数组是第二位的因为它能暴露你对超过一半的理解。n 1 时唯一的元素出现 1 次1 0.5所以它就是答案。所有解法在这个输入上都应该返回它自己。排序版本取nums[0 // 2] nums[0]正确摩尔投票版本扫一遍候选就是它复核 1 0也正确。但如果你在排序版本里写成nums[nums.length/2 - 1]n 1 时下标变成 -1直接崩。负数是第三位的主要影响哨兵值的选择。如果你用-1或者0表示未初始化而数组里恰好有 -1 或 0逻辑就会串。我在代码里见过用Integer.MIN_VALUE当哨兵的这个更危险因为Math.abs(Integer.MIN_VALUE)会溢出成负数后续如果对 candidate 做了绝对值运算就炸了。最稳的做法是用一个独立的布尔变量标记是否已初始化而不是拿数据域里的某个值当哨兵。还有一类输入值得单独测答案是数组中最大或最小的元素比如{-1000000}或者{2147483647, 2147483647, 1}。这类输入主要考验你代码里有没有隐藏的类型转换问题比如把long和int混着比较。4.2 Java 里 Integer 的 陷阱这个坑严格说不属于这道题的算法范畴但只要你用 Java 写哈希版本或者泛型版本几乎必踩。在 Java 中如果nums的类型是int[]那x candidate比较的是数值没问题。但如果你的函数签名是ListInteger nums或者Integer[] nums那比较的就是对象引用。而 Java 对 -128 到 127 之间的 Integer 有缓存池所以小整数的会碰巧返回 true大整数就会返回 false。这种小数据对、大数据错的 bug 极难排查因为你的测试用例里数字往往都很小。Integer a 127, b 127; System.out.println(a b); // true因为走缓存池 Integer c 128, d 128; System.out.println(c d); // false两个不同对象 System.out.println(c.equals(d)); // true正确比较方式所以只要涉及包装类型一律用equals()或者先intValue()拆箱再比。这个建议看起来是老生常谈但我见过它在真实项目里造成的线上问题金额字段用 Integer 存分超过 127 之后比对全错排查了半天。还有一个相关的坑Arrays.asList(1, 2, 3)返回的 List 是固定长度的往里面add会抛UnsupportedOperationException。这不直接相关但同属Java 集合的隐藏行为这个家族一起记下来不吃亏。4.3 从超过一半追问到超过三分之一这是这道题最经典的追问链路几乎每个认真的面试官都会问。问题变成找出所有出现次数超过 n/3的数字。注意这里从找出一个变成了找出所有并且答案最多有两个——因为三个超过 1/3 的数加起来就超过 1 了矛盾。对应的算法是摩尔投票的推广版维护两个候选和两个计数。public ListInteger majorityThird(int[] nums) { int c1 0, c2 0, n1 0, n2 0; for (int x : nums) { if (n1 0 x c1) n1; else if (n2 0 x c2) n2; else if (n1 0) { c1 x; n1 1; } else if (n2 0) { c2 x; n2 1; } else { n1--; n2--; } // 三个不同阵营各消一个 } // 复核 ListInteger res new ArrayList(); int t1 0, t2 0; for (int x : nums) { if (n1 0 x c1) t1; else if (n2 0 x c2) t2; } if (n1 0 t1 nums.length / 3) res.add(c1); if (n2 0 t2 nums.length / 3) res.add(c2); return res; }这里有几个非常容易写错的地方我逐个说。第一判断顺序不能乱。必须先判断当前元素是否等于已有候选再判断是否有空位最后才是三消。如果顺序反了比如先判断空位那么当n1 0时会把一个本该给 c2 加票的元素塞给 c1结果直接错。第二复核阶段的判重。极端情况下 c1 和 c2 可能指向同一个值比如数组全是同一个数第二个候选永远占不到位置所以复核时要用else if保证每个元素只被计入一个候选否则会把同一个值的票数翻倍误判成多数。或者老老实实对两个候选分别做两次独立计数再对结果去重。第三n1 0这个前置条件不能少。当计数归零后对应的候选值就失效了此时x c1不应该再加票。这是很多人照着 n/2 版本的直觉写过来时最容易漏的。推广到一般情况 n/k就需要维护 k-1 个候选。原因很简单如果存在超过 n/k 的数最多只有 k-1 个这样的数k 个超过 n/k 的数加起来就超过 n 了。所以准备 k-1 个位置就够装下所有可能的答案多一个都是浪费。5. 把结论推广到 n/k通用摩尔投票的写法与取舍5.1 为什么要维护 k-1 个候选上一节提到维护 k-1 个候选这里把理由讲透。设数组长度为 n我们要找出所有出现次数超过 n/k 的数。假设有 m 个这样的数记为x1, x2, ..., xm每个的出现次数都大于 n/k。那么它们的出现次数之和大于m * n/k。由于这些数字互不相同它们的出现次数之和不可能超过 n所以m * n/k n即m k也就是m ≤ k-1。这个不等式就是全部理由。它说明不管数组长什么样符合超过 n/k条件的数字最多 k-1 个所以分配 k-1 个槽位一定有富余一个都不会漏。反过来如果你只分配 k-2 个槽位就存在构造反例的空间当真的有 k-1 个数字都接近 n/k 时多出来的那个没地方待会被提前抵消掉。所以 k-1 是紧的下界不多不少。顺带说清楚抵消这个动作在推广版里的形态。原版是两个不同阵营各消一个推广版是k 个不同阵营各消一个。每次扣除 k 个不同元素剩余元素总数减少 k。同样可以证明多数性不变设某个目标 x 出现次数为kx总数为nkx n/k。消一次kx最多减 1总数减 k那么kx - n/k这个量单调不减。所以kx n/k恒成立最终 x 必然占据一个槽位。代码里体现这个k 消的写法就是那个else { n1--; n2--; }分支——当当前元素既不等于任何候选、也没有空位时说明它开启了一个新阵营于是所有已有阵营各消耗一个。在 k3 的场景下就是两消二实际上是三方混战两个候选各减 1新元素也不占位等价于消掉了三个不同元素。5.2 一次遍历的更新顺序与常见写错点推广版的更新逻辑我建议严格按这个顺序写别自作聪明调整若x等于某个非空候选的候选值该候选计数 1结束本轮否则若有候选计数为 0用x占据该槽位计数置 1结束本轮否则所有候选计数 -1结束本轮对应的代码骨架就是上面那段。把这四步顺序调换几乎必然出错我整理了一份错误写法对照表方便你 check 自己错误写法现象根因先判空位再判相等候选被同一元素重复占用空槽位抢走了本该加给已有候选的票候选为空时仍执行x c1已失效的旧候选继续吸票漏了n1 0的前置条件复核时不加else if两个候选票数相加后翻倍同一元素被计入两个候选用 n/k作为复核条件结果多出边界值题目要求严格大于不是大于等于忘记过滤n1 0的候选输出 0 或者残留值槽位从未被占用候选值是初始化的脏数据最后一条特别值得强调。假设数组是{1, 2, 3}k 3。第一轮 1 占 c1第二轮 2 占 c2第三轮 3 进来触发三消n1 和 n2 都归零。此时 c1 还是 1c2 还是 2但它们都失效了。如果你不复核n1 0直接拿去统计虽然最终的t1 n/3判断会拦住1 只出现 1 次不大于 1但如果数组是{1, 1, 1, 2, 2, 3}这种就可能出现 c1 的阶段计数已归零但真实次数够多的情况——这是安全的因为复核用的是真实计数。真正危险的是如果候选人压根没被复核对那就会输出脏数据。所以我的写法里两个条件都留着n1 0 t1 n/3双重保险。5.3 复杂度与工程上的实际选择推广版的时间复杂度是 O(n * (k-1))不是。遍历过程中对每个元素最多和 k-1 个候选比较一次所以每一轮是 O(k)总时间 O(nk)。当 k 是常数时比如 k 3、k 4这就是 O(n)。空间 O(k)。真正的取舍在于当 k 变大时摩尔投票的优势迅速衰减。比如你要找出现次数超过 n/1000 的数那就要维护 999 个候选每个元素都要跟 999 个候选比较一遍时间变成 O(1000n)而哈希表版本是 O(n) 加一次遍历反而更快。而且 999 个候选的数组维护起来代码可读性和出错概率都不是一个量级。所以我的判断标准很简单场景推荐方案理由k 2超过一半摩尔投票常数极小空间 O(1)代码六行k 3超过三分之一摩尔投票推广版两只候选代码仍可控k ≥ 10哈希表 复核候选数组维护成本超过收益k 由参数动态传入哈希表 复核通用性好不易写错有外部依赖要求 O(1) 空间摩尔投票别无选择另外还有一个工程上的现实考量摩尔投票对数据流式输入特别友好。因为它只需要两个变量可以在不存储任何历史数据的前提下处理无限长的数据流——这在处理日志流、传感器数据流时是刚需。哈希表版本就做不到因为你要保存所有不同元素的计数内存会随基数增长而膨胀。这个特性在面试时说出来会很加分因为它证明你想的不只是怎么能过题而是这个算法在什么形态的数据上有不可替代性。6. 五种解法横向对照与我的取舍建议6.1 一张对照表把上面所有解法摊在一张表里优劣一目了然解法时间空间答案存在时正确答案不存在时行为代码量哈希计数O(n)O(n)是可正确返回失败值中排序取中位O(n log n)O(n) 或 O(log n)是静默返回错误值极短快速选择平均 O(n)最坏 O(n²)O(log n) 栈是静默返回错误值长摩尔投票不复核O(n)O(1)是静默返回错误值极短摩尔投票 复核O(n)O(1)是正确返回失败值短表里最值得注意的是第三列和第四列。答案存在时正确这一列所有解法都是是这也是为什么很多人觉得自己做对了——他们只在题目给的样例上测过。真正区分度在第四列三个解法会在答案不存在时静默返回错误值而它们的代码都不会报错。排序版本和快速选择版本之所以也静默出错是因为中位数是答案这个结论本身就依赖存在多数元素这个前提。前提不成立时中位数只是中位数跟多数毫无关系。比如{1, 2, 3, 4}排序后取下标 2 得到 3但 3 只出现了一次。6.2 我在实际取舍时的判断顺序刷题时我们通常冲着最优解去但真实写代码时的决策链其实是反过来的。我自己总结的判断顺序是第一步看题目有没有保证。如果输入一定满足存在超过一半的数那就直接用摩尔投票 复核复核这一趟几乎不要钱何必省。如果题目不保证那更是必须复核没有商量余地。第二步看数据规模。n 小于一万哈希表版本往往是最快的实际选择因为它的分支预测友好、缓存命中率高而且实现简单不易错。这时候上摩尔投票属于为了优雅牺牲可读性如果这段代码会被别人维护未必划算。第三步看内存约束。如果是嵌入式环境、移动端、或者需要处理 GB 级数据流那 O(1) 空间的优势是压倒性的摩尔投票是唯一选择。第四步看是否需要流式处理。数据只能遍历一次且不能全量缓存时摩尔投票几乎是唯一的通用答案。这四步走完最高级的算法不一定被选中但一定被选中了最适合的那个。我见过太多人一上手就写摩尔投票结果在一个 n 20 的配置校验场景里写出六行别人看不懂的代码最后被 review 打回来。算法选择是手段不是目的。最后分享一个我自己的记忆方法比死记代码靠谱把摩尔投票记成一个擂主一条命遇同门加血遇异门掉血血空换人。这个模型里多数元素对应的是一个阵营的人数超过全场一半那么无论中间怎么打最后站在擂台上的一定是人数最多的那个阵营。想不起来代码的时候把这个画面在脑子里过一遍条件分支自然就写出来了。至于这题还能往哪扩我平时会顺手练两个方向一个是把它和求众数结合讨论出现次数最多的 k 个数这种 Top-K 问题那就要上堆或者桶排序另一个是把它和数据流中位数结合起来看看两个看着不相关的题目在流式处理这个约束下会碰出什么火花。这两个方向我都踩过一些坑回头单独整理。