你要是刷过 LeetCode 的“多数元素”这题大概都有过这样一种体会题目本身一句话就能看懂暴力解法闭上眼睛都能写但面试官一句“能不能只用一次遍历、常数空间”瞬间就让很多人卡壳。169 题的核心解法摩尔投票法正是为这个约束量身定做的而用C 语言实现它时又藏着几个非常容易踩的细节。这篇博文我不打算只念一遍题解而是把题目想问什么、投票算法的直觉从哪来、代码每一行为什么这么写、以及自己实际调试中踩过的坑都摊开来讲。适合正在啃LeetCode 经典 150 题的人也适合准备面试、想真正理解算法原理而不是只背模板的C 语言学习者。1. 一道看似简单的题多数元素到底想问什么1.1 题目说了什么又没说什么LeetCode 169 题的描述很短给定一个大小为 n 的数组 nums返回其中的多数元素。多数元素指出现次数大于n/2向下取整的元素。题目额外保证数组非空并且给定的数组总是存在多数元素。这里有两个容易被忽略的词。第一个是“大于”而不是“大于等于”比如数组 [1,1,2,2]n4n/221 和 2 各出现 2 次都不满足“大于 2”所以这种数组不符合题意。第二个是“总是存在”这句话虽然看起来只是保证但它的真正含义是在多数元素和所有非多数元素之间存在着一条铁律——多数元素的数量大于其他所有元素的数量之和。比如说数组长度是 11多数元素至少出现 6 次剩下的 5 个元素就算全部联合起来也压不过它。这条铁律就是整个摩尔投票法成立的根基。顺带补充一个基础题目给出的元素范围是 int 范围可正可负数组长度最大可以达到 5×10^4这意味着你不能把“数值本身”当成数组下标去计数因为负数没法当下标正数范围也太大了。这个限制直接堵死了一条 C 语言里最朴素的“桶计数”方案。1.2 通法盘点暴力、哈希、排序各有各的账要算看到这题大多数人第一反应是暴力。两重循环外层枚举每个元素内层统计它出现几次看到次数大于 n/2 就返回。时间复杂度 O(n^2)在 LeetCode 上面对 5×10^4 的数据规模大概率直接超时。它不是不能用但只能作为面试时“我先说个最笨思路”的铺垫。第二个思路是哈希表。一次遍历用哈希表统计每个元素出现次数再扫一遍找次数超过阈值的结果。时间复杂度 O(n)空间 O(n)。这个思路在 Java 里用 HashMap 写起来很舒服但在 C 语言里就麻烦一些标准库没有现成的哈希表要么自己用链地址法手写一个要么引入 uthash 这种第三方头文件。在面试现场徒手写 C 哈希表时间成本不低而且容易在扩容、冲突处理这些细节上卡壳。第三个思路是排序。因为多数元素超过一半所以数组排完序之后n/2 下标处那个元素必然是多数元素。时间 O(n log n)空间取决于排序算法归并排序需要 O(n)快速排序原地只需要 O(log n) 的栈空间。这个解法代码量极少作为“我能立刻想到的优化版”说出来没问题但面试官大概率会追问一句能不能不排序、不用额外空间线性时间内搞定能接下这句追问的就是摩尔投票法。三种方案放在一起对比差距就很直观了解法时间复杂度空间复杂度C 语言实现难度典型场景暴力两重循环O(n^2)O(1)极低小数据集教学哈希表计数O(n)O(n)高需手写表通用统计排序取中位O(n log n)O(1) 或 O(n)低可原地排序的场景摩尔投票O(n)O(1)低大数组、流式数据1.3 为什么面试官盯着摩尔投票不放这题被归入 LeetCode 经典 150 题并不是因为它难而是因为它是一个典型的“你知不知道这个套路”的题。暴力解法谁都会哈希计数是通用技能排序取 n/2 是取巧只有摩尔投票能把“只需要两个变量、一次遍历”这件事做到极致。很多面试官喜欢拿它做梯度题先让候选人写出能跑通的解再逐步加限制条件看能不能走到最优解。更重要的是摩尔投票法不光能背代码它背后的“抵消”思想可以迁移到不少场景比如流式数据里找热点项、分布式系统里各节点合并统计、甚至某些推荐场景下找占比优势明显的品类。面试官问你原理本质上是想确认你是真懂还是背模板。所以接下来的重点不在代码而在把原理揉碎了讲清楚。2. 摩尔投票法一次遍历背后的数学直觉2.1 “删掉两个不同元素”的抵消思想摩尔投票法的通俗理解可以压缩成一句话每次找出两个不同的元素把它们同时删掉那么到最后剩下来的元素就是多数元素。因为多数元素比所有非多数元素加起来还要多所以在两两抵消的过程中最后能活下来的必然是它。举个例子数组 [2,2,1,1,1,2,2]。我们从左往右模拟“删除一对不同元素”第一步 2 和 1 抵消第二步 2 和 1 抵消此时数组剩 [1,2,2]第三步 1 和 2 抵消最后剩一个 2。这个 2 就是多数元素。注意抵消的顺序并不会影响最终结果因为每次删掉两个不同元素多数元素在剩余数组里的“绝对优势”都不会被逆转。那么怎么用迭代的方式表达“抵消”呢答案就是两个变量一个 candidate 记录当前可能的多数元素一个 count 记录它的“净票数”。遇到和 candidate 相同的元素count 加一遇到不同的元素count 减一。当 count 归零时意味着当前候选者在已经扫描过的这一段里被完全抵消了于是把下一个元素设为新的 candidate。这个过程本质上就是在模拟“两个人打架一换一最后站着的是人多的一方”。2.2 严格证明为什么幸存者一定是多数元素直觉归直觉面试时最好能给出干净利落的证明。我常用的是“前缀删除不改变多数性质”的思路。假设整个数组中存在多数元素 M总出现次数大于 n/2。扫描过程中每当 count 归零我们把已经扫描过的这一段看成一个整体。在这段前缀里candidate 被完全抵消说明不同元素之间形成了一一配对这段前缀中没有任何元素能成为多数。现在考虑剩余的未扫描部分因为 M 在整个数组中是多数而前缀这段又不存在多数那么 M 在剩余部分中依然是多数。也就是说删掉这段前缀之后问题变成了一个规模更小的相同问题。这样一直删除最后剩下的数组中必然只有一个元素而这个元素就是 M。更形式化的说法是每一轮 count 减一都等价于删除了一个 candidate 和一个不同的元素多数元素 M 始终没有被删除得超过它的总数因此最后留下的 candidate 只能是 M。我还见过另一种等价证明用“正负票”来理解把对 candidate 的支持算作 1把反对算作 -1。当一个区间内净票数为 0说明这段区间对任何元素都投不出优势票。全局多数元素的总票数是正的所以它赢在那些净票数为正的区间里。最终 candidate 停在哪里哪里就是它的票仓。这个理解方式在解释为什么“count 减到 0 后要换人”时特别直观。2.3 题目保证存在不等于你可以不防御LeetCode 169 明确说了“总是存在多数元素”所以在提交时直接返回最后的 candidate 就能通过。但我在实际写代码时仍然建议至少脑内过一遍“如果没有多数元素会怎样”。考虑一个反例[1,2,3,4]。用摩尔投票跑一遍candidate 从 1 变 2 变 3 变 4最后 candidate 是 4。可 4 只出现了一次根本不是多数元素。这说明摩尔投票算法本身只能保证“如果多数元素存在那么最后留下的 candidate 就是它”它并不能区分“候选者真的是多数”还是“只是最后一个幸运儿”。所以在真实项目或面试追问中标准做法是第一遍扫描得到 candidate第二遍扫描统计 candidate 的出现次数确认次数是否大于 n/2。这就是摩尔投票的完整形态也是很多变种题的通用出口。题目虽然不要求但写出这一步能让面试官看到你考虑问题足够严密。3. C 语言落地从伪代码到可运行代码3.1 核心函数逐行解读candidate 和 count 的配合先看最经典、最容易写的版本int majorityElement(int* nums, int numsSize) { int candidate 0; int count 0; for (int i 0; i numsSize; i) { if (count 0) { candidate nums[i]; } if (nums[i] candidate) { count; } else { count--; } } return candidate; }这个版本的关键在循环体里的两个 if 的顺序。当 count 为 0 时先把当前元素设为新的 candidate然后再判断“当前元素是否等于 candidate”——刚设完就比结果必然是相等于是 count 变成 1。这相当于给新候选者补上了第一张赞成票。另一个常见写法是先把 candidate 初始化为 nums[0]count 初始化为 1然后从下标 1 开始遍历int majorityElement(int* nums, int numsSize) { int candidate nums[0]; int count 1; for (int i 1; i numsSize; i) { if (nums[i] candidate) { count; } else if (--count 0) { candidate nums[i]; count 1; } } return candidate; }这个版本逻辑更紧凑但有一个容易写错的点在执行else if (--count 0)时说明遇到了一个不同元素这一张反对票已经消耗掉了。此时如果 count 刚好归零新候选者就是当前这个“不同元素”它必须占一个名额所以 count 要重置为 1而不是 0。我见过不少人在这写 0结果后面的票数全部错位。两种写法都能过我更推荐第一种。不是因为效率而是因为它把“选候选者”和“投票”两件事在逻辑上拆开了出问题时更容易用 print 调试。3.2 完整的本地编译测试不只跑通还得会验证单写函数只能证明思路作为学习者我建议你把完整测试程序落到本地。我自己的测试代码长这样#include stdio.h int majorityElement(int* nums, int numsSize) { int candidate 0; int count 0; for (int i 0; i numsSize; i) { if (count 0) { candidate nums[i]; } if (nums[i] candidate) { count; } else { count--; } } return candidate; } int main(void) { int arr1[] {3, 2, 3}; int arr2[] {2, 2, 1, 1, 1, 2, 2}; int arr3[] {5}; int arr4[] {-1, -1, 1}; printf(%d\n, majorityElement(arr1, 3)); // 期望 3 printf(%d\n, majorityElement(arr2, 7)); // 期望 2 printf(%d\n, majorityElement(arr3, 1)); // 期望 5 printf(%d\n, majorityElement(arr4, 3)); // 期望 -1 return 0; }编译命令在 Linux 或 Mac 下是gcc -stdc99 -Wall -o majority majority.cWindows 下用 VSCode 配好 C 环境或者直接装 MinGW 的 gcc 也行。环境这种东西没有标准答案我刚学 C 语言时用的还是古老的 VC 6.0现在大家普遍用 VSCode 加插件或者 CLion能编译能调试就足够。这里多说一句调试习惯。我在初学阶段根本不敢用 gdb觉得一堆命令行看不懂。后来养成一个笨办法遇到结果不对就在循环里临时加一行printf(i%d candidate%d count%d\n, i, candidate, count);。跑一遍之后候选者的变化轨迹就全清楚了。等你觉得 printf 不够用再回头学 gdb 会事半功倍。3.3 C 语言独有细节指针参数、数组退化与边界保护第一点函数签名int* nums和int nums[]在 C 语言里完全是等价的数组作为函数参数传递时会退化成指向首元素的指针。所以函数内部不能用sizeof(nums)/sizeof(nums[0])来求数组长度nums 在这里是个指针那样算出来的结果没有任何意义。必须依赖传入的 numsSize这也是 LeetCode 后台调用这个函数时总是把长度一起传进来的原因。第二点数组下标从 0 开始循环条件应该是i numsSize。手滑写成i numsSize会越界访问读到一个不确定的垃圾值。在本地小数组上可能碰巧不崩但 LeetCode 的检验数据一多很容易出现随机错误。排查这类问题的一个小技巧是如果程序答案时对时错优先检查所有循环边界。第三点防御空数组。虽然题目说数组非空但如果你自己写工具函数最好加上空数组保护。C 语言里访问空指针或者非法地址会直接段错误不像其他语言会抛异常。一个稳妥的写法是函数开头判断numsSize 0时返回一个约定值比如 -1。如果你写的是带验证的完整版本这个保护尤其必要因为验证循环也要遍历数组有可能连第一次遍历都进不去。4. 现场调试高频错误与排查思路实录4.1 三个我真实踩过的坑给你做成检查表第一个坑是把函数开头的初始化写成了int candidate -1;或者随便一个固定值然后忘记在循环里处理 count 为 0 的情况。这种写法对大多数输入都能碰巧通过但对那些多数元素恰好等于你初始值的用例会得到错误答案。正确做法是不要依赖初始值的“幸运”要么在 count 为 0 时重新设置候选者要么直接把 candidate 初始化为 nums[0]。第二个坑是循环里的两个 if 顺序颠倒。如果把if (nums[i] candidate)写在前面if (count 0)写在后面那么当 count 为 0 时程序会先拿当前元素和旧候选者比较再更新候选者更新完后这个新候选者白白丢掉了一张属于它的初始票。这种 bug 很隐蔽因为大部分用例还能过直到你构造出[1,2,1]这种交替序列才会暴露。第三个坑来自第二种写法else if (--count 0)之后把 count 重置为 0。表面上看新候选者刚上任count 从 0 开始似乎很正常但别忘了当前这个元素已经被当作“反对票”消耗了一次它必须作为新候选者的第一张支持票存下来。所以这里必须写count 1。我自己就在这个分号前栽过跟头后来每次写都会在心里默念减票和换人不能同一步完成换人要发新票。错误表现可能原因检查位置结果总是数组最后一个元素缺少“count 归零更新 candidate”的逻辑循环体开头交替序列求出错误值两个 if 顺序写反新候选者没有初始票投票逻辑单元素数组越界candidate 初始化访问 nums[0] 前未判空函数入口变体写法结果差一换候选者后 count 被重置为 0else if分支4.2 性能验证为什么这是时间和空间的极限时间上摩尔投票只做了一次线性扫描加第二遍验证的话也就是从头到尾再扫一次。每个元素至多被看一眼时间复杂度 O(n)。这个下界是跑不掉的任何算法都必须读一遍全部数据才能确定谁是多数元素不存在比 O(n) 更快的可能。空间上整个算法只用了两个 int 变量无论数组长度是 1 还是 10^9额外空间都是常数量级也就是 O(1)。作为对比哈希表方案的空间开销随数据规模线性增长排序方案无论是归并的临时数组还是快排的递归栈都做不到严格的 O(1) 附加内存。所以“一次遍历 两个变量”不是巧合而是这个算法最锋利的点它不申请额外内存完全靠消除法内算出结果。很多同学刷题只看“能不能 AC”忽略复杂度背后的意义。我的建议是提交通过之后至少手动算一遍两个复杂度的上界并在笔记本上写一句“为什么这个复杂度是最优的”。这个习惯对面试帮助很大因为面试考的就是这个“为什么”。4.3 面试追问清单怎么从 169 题延伸到真正的高频考点面试官在 169 题上最常见的追问是“如果数组中可能没有多数元素你怎么办”。答案前面已经提过第一遍选出 candidate第二遍统计出现次数做验证不满足就返回一个表示“不存在”的值。这个追问几乎必考因为题目本身的保证条件一旦撤掉候选者就可能是假的。第二类追问是“我不需要值我需要返回多数元素的下标怎么改”。其实很简单第一遍照常找出 candidate第二遍扫描时遇到值为 candidate 的元素直接返回这个下标。由于可能存在多个相同元素返回第一个遇到的即可。第三类追问是“如果数据是源源不断的流式输入内存装不下怎么办”。这个问题正撞在摩尔投票的枪口上因为它只需要两个变量天然支持流式处理来一个元素更新一次 count 和 candidate过去的数据直接丢弃不需要保留历史。这时候你可以顺势提一句这种只依赖少量状态、一遍扫完的算法就是典型的流式算法streaming algorithm在日志分析、实时统计场景里有实际价值。面试的真相是算法题的代码只是入场券代码背后的边界讨论、方案取舍、复杂度分析才是分水岭。刷 169 题时多想一想“没有多数元素”“要下标”“数据是流”这几种变化比刷十道同类型简单题更值得。5. 摩尔投票法的变体从 n/2 到 n/3 再到真实场景5.1 升级版出现次数超过 n/3 的元素怎么找LeetCode 229 题是 169 题最经典的变体找出数组中出现次数大于 n/3 的所有元素。这题的数学前提是超过 n/3 的元素最多只有两个。比如数组长度 9超过 3 次的元素最多能有 2 个不可能出现 3 个都超过 3 次的情况。基于这个前提摩尔投票被扩展成“双候选者”版本维护两个候选者 candidate1、candidate2以及两个计数器 count1、count2。遍历时先分别匹配两个候选者匹配上就加票匹配不上时看哪个候选者票数归零就替换掉哪个如果两个都有票说明当前元素同时反对这两个候选者于是两个计数器都减一。这个流程模拟的是“三个不同的人打架三个一起消耗”。核心循环大概长这样int candidate1 0, candidate2 1; int count1 0, count2 0; for (int i 0; i numsSize; i) { if (nums[i] candidate1) { count1; } else if (nums[i] candidate2) { count2; } else if (count1 0) { candidate1 nums[i]; count1 1; } else if (count2 0) { candidate2 nums[i]; count2 1; } else { count1--; count2--; } }注意这里的判断顺序先匹配候选者再补空缺最后才集体抵消。如果把“补空缺”提到“匹配候选者”前面候选者的实际票数会被低估甚至出现同一个元素同时占两个候选位的情况。写完后同样不能直接返回两个候选者必须重新扫描数组统计它们真实出现的次数只把超过 n/3 的加入结果。这道题能让你体会“算法负责猜验证负责审”的工程思维。5.2 真实场景说明不止是刷题它本身就是流式统计有人会问这种只能找“占比绝对优势元素”的算法平时真能用上吗我的答案是能但要对它的适用范围有清醒认知。最常见的场景是内存受限条件下的热点发现。比如一个服务器每分钟产生海量访问日志你想知道这段时间内有没有“压倒性”的请求来源 IP。如果把所有 IP 存进哈希表内存会撑不住但用摩尔投票你只需要两个变量就能在线维护一个最有嫌疑的候选者。类似地在投票系统的实时计票、传感器数据流里找异常主导值、甚至在某类推荐策略里判断单一品类是否占据绝对份额摩尔投票的空间优势都会显现。但它不是万能的。如果数据分布很均匀没有哪个元素占比超过一半candidate 就会频繁更替算法最终给出的结果只能当“疑似对象”必须配合验证步骤。另外它只能告诉你“谁是”不能告诉你“每个元素各占多少比例”后者需要更复杂的 sketch 类算法。所以更准确的说法是摩尔投票是流式统计工具箱里的一把专用扳手拧对了螺丝非常好用但别指望它能干全套维修。我在实际工作中用过一次类似思路一个嵌入式设备的内存只有几十 KB要统计一段时间内采集数据中出现频率最高的状态值。当时第一反应是哈希表但内存预算根本不允许。后来想起摩尔投票用两个全局变量就解决了代价是只能知道“绝对高频项”但对那个场景来说已经足够。这也是我强烈建议 C 语言学习者认真吃透这题的原因它教的不只是算法还是一种“如何在极端受限环境下用最少状态解决问题”的思维方式。我个人刷这题的经验是不要急着背代码先在草稿纸上把[2,2,1,1,1,2,2]这个数组从头到尾模拟一遍看着 count 怎么增、怎么减、candidate 什么时候换人。等你闭上眼睛都能把这个过程画出来摩尔投票法就真正属于你了。之后遇到 n/3、验证缺失等变体你自然知道该往哪个方向改。如果时间紧张至少记住两件事算法存在的前提是多数元素有绝对数量优势拿到候选者之后永远想一下是否需要验证。