1. 看到“多数元素”这道题先别急着写哈希表LeetCode 169 是经典150题里讨论度很高的一道入门题。题目很简短给定一个大小为 n 的数组 nums返回其中的多数元素。多数元素是指在数组中出现次数大于 n/2 的元素。你可以假设数组非空并且给定的数组总是存在多数元素。我第一次做这道题时第一反应是“统计一下不就出来了”但真要用 C 语言把边界、空间复杂度和各种解法放在一起看才发现这道题真正要练的不是“找数”而是对空间复杂度的敏感度。我在 C 语言和算法题上打交道有七八年了LeetCode 高频题基本都反复写过。169 这道题我建议所有刷题的人都亲手实现一遍摩尔投票法不仅因为它是 LeetCode 经典150题里的常客更因为这种“抵消”思想在面试白板题里经常能派上用场。这篇文章我就用 C 语言把题目、原理、实现、踩坑一次性讲透适合刚刷 LeetCode 的 C 语言新手也适合想快速复习摩尔投票法的老手。1.1 题目到底在考什么多数元素出现次数大于 n/2注意这里的 n/2 是整数除法在 C 语言里就是n / 2。n7 时出现次数大于 3 就是至少 4 次n8 时出现次数大于 4 就是至少 5 次。多数元素保证存在并且唯一这一点由“出现次数大于 n/2”直接推出如果存在两个不同元素都出现超过 n/2 次它们的次数之和就会超过 n显然不可能。题目真正的考点不是让你实现一次“查找出现最多元素”的扫描而是考察你不借助额外存储能不能做到。很多人在面试里脱口而出“用哈希表计数”这当然能过但它没有抓住 169 的题眼。LeetCode 把这题放进热门一百多一些刷题单里但它要求的最优空间是 O(1)这一点在面试追问里非常致命。你要是没法在不用哈希的情况下解释清楚很容易被认为对算法的空间复杂度不敏感。1.2 常规解法的两笔账时间和空间先摆一笔传统解法的账。第一笔账是暴力法。两层循环外层枚举候选元素内层统计出现次数找到次数大于 n/2 的元素就返回。典型的写法是这样的int majorityElementBruteForce(int* nums, int numsSize) { for (int i 0; i numsSize; i) { int cnt 0; for (int j 0; j numsSize; j) { if (nums[j] nums[i]) { cnt; } } if (cnt numsSize / 2) { return nums[i]; } } return 0; }这个写法很好懂但时间复杂度 O(n^2)。LeetCode 的测试数据如果 n 到十万级别基本就会超时。它只适合用来理解题意不适合作为最终答案。第二笔账是哈希表计数。C 语言写哈希表比较麻烦需要自己实现开放寻址或链表法或者借助 glib 这类库的哈希容器。在 C 或 Python 里哈希法很容易写但空间复杂度是 O(n)。如果面试官在 169 上追问一句“能不能 O(1) 空间”哈希表答案当场失效。还有一条思路是先排序再取中间元素。因为多数元素出现次数超过一半数组排序后它一定会落在n/2这个位置。用 C 标准库的qsort实现非常短int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); } int majorityElementSort(int* nums, int numsSize) { qsort(nums, numsSize, sizeof(int), cmp); return nums[numsSize / 2]; }排序法的时间复杂度是 O(n log n)空间复杂度取决于qsort的实现通常是 O(log n) 的递归栈。对于大多数场景它已经足够快代码也非常可靠。但它不是线性时间面试题只要限定“线性时间”排序法就会被排除。所以这道题的最优解就是接下来要说的摩尔投票法一趟扫描完成时间 O(n)额外空间 O(1)。这也是 LeetCode 特意把它选进经典150题的原因之一。1.3 问题里容易被忽略的“保证”做题时一定注意题干最后一句给定的数组总是存在多数元素。这是一个很强的约束意味着你写的函数在任何测试用例下都不会遇到“不存在多数元素”的情况代码可以直接假设最终候选者有效。这个保证在实际工程里很少见但在算法题里非常常见。它让摩尔投票法的实现变成一段非常干净的循环不需要在返回前再验证一次出现次数。如果你是第一次接触这类题建议先按“存在多数”写一版再自己改成“可能不存在多数”的防御版本两版都跑一遍才能真正理解为什么需要额外的“验证阶段”。2. 摩尔投票法一次遍历靠“抵消”找出赢家摩尔投票法英文通常叫 Boyer-Moore Majority Vote Algorithm。注意用来做字符串匹配的 Boyer-Moore 算法也是这两个人的名字但两者不是同一回事刚刷题的人容易搞混。它解决的问题非常专一在一组数据里找出出现次数超过一半的元素时间 O(n)空间 O(1)。核心思想可以这样记把数组想象成一场多对多的消耗战。2.1 直觉多数的优势在于“一对一兑子”假设数组里有两类角色多数元素 M 和其他元素。M 的数量大于其他所有元素数量之和。现在让任意两个不同元素互相“同归于尽”重复这个过程最后剩下的元素一定是多数元素吗答案是肯定的因为 M 的数量优势在大盘上始终存在。每次抵消拿走一个 M 和一个非 MM 的净剩余都比非 M 的净剩余多。哪怕中间出现非 M 之间互相抵消消耗的也只是非 M 的数量对 M 没有任何坏处。这就是摩尔投票法的直觉来源用一个“候选人”和一个“票数”模拟抵消过程。遇到同类就加一票遇到异类就减一票当票数归零时说明当前扫描区间内的元素已经全部抵消干净可以选下一个元素当候选人继续。2.2 算法规则候选人与计数器整个算法只需要两个变量candidate当前选中的候选人。count候选人的“净票数”。初始时candidate可以随便设count设为 0。遍历数组 nums如果count 0把当前元素赋给candidate并令count 1。否则如果nums[i] candidate执行count。否则执行count--。遍历结束后candidate就是多数元素。我实际跑一遍[3, 2, 3]来演算步骤当前元素进入循环前 (candidate, count)执行动作离开循环时 (candidate, count)13(0, 0)置为候选人(3, 1)22(3, 1)异类抵消(3, 0)33(3, 0)重新置为候选人(3, 1)最后返回 3正确。这个例子能直观看到count归零后换候选人的过程。如果数组是[1, 2, 1, 3, 1, 4, 1]多数元素 1 不断换血但它数量占优最后总能在某个轮次存活下来。2.3 为什么剩下的一定是多数元素不严谨但够用的证明要证明算法的正确性用反证法最舒服。假设数组长度为 n多数元素 M 出现次数为 k满足 k n/2。算法结束时candidate不是 M说明 M 在整个抵消过程中被“完全抵消”了。每次 M 被抵消必然有一个非 M 元素与它配对非 M 之间互相抵消只会让非 M 的数量更少。所以要让 M 被完全抵消至少需要 k 个非 M 元素与它配对。这意味着非 M 元素总数至少是 k总元素数 n 2k得到 k n/2这与 k n/2 矛盾。这个推导不需要你背下来你只需要抓住一句话数量超过一半的元素不可能被其他元素成对消灭。剩下的候选人只能是多数元素。2.4 边界情况偶数长度与没有多数怎么办数组长度为偶数时比如[1, 1, 2, 2]多数元素不存在算法给不出可靠答案。LeetCode 169 明确保证存在所以不用管。但如果是面试题改成了“找出现次数最多的元素”或者“可能不存在多数”你就必须多做一个验证步骤再遍历一遍数组统计candidate的真实出现次数如果确实大于 n/2 才返回否则返回一个“不存在”标志。另一个容易误解的点是算法过程中count变成 0不代表当前元素被淘汰而是说明扫描到当前位置为止候选人的净优势已经抵消干净。此时直接把下一个元素作为新候选人即可。如果真有占多数的元素它的净票数不可能在某个前缀区间归零因为一旦归零就说明它在那个区间里并不占优这会违反多数元素的全局性质。3. C 语言实现从函数签名到边界检查进入代码环节。这一节我直接以 LeetCode 给出的 C 语言函数原型作为入口把实现拆成几行讲清楚再补几个 C 语言做题时容易出问题的点。3.1 LeetCode 给出的函数原型在 LeetCode 的 C 语言题目页里你会看到这样的空函数int majorityElement(int* nums, int numsSize){ }返回类型是int参数是数组指针和数组长度。注意numsSize用的是int而不是size_t这是 LeetCode 题目的惯例。你只需要在函数内部用两个局部变量完成扫描最后返回一个int。不需要动态分配内存也不需要释放资源。3.2 标准实现与逐行解释最标准的摩尔投票法实现如下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]; count 1; } else if (nums[i] candidate) { count; } else { count--; } } return candidate; }整个过程只用两个局部变量跑完numsSize个元素后返回candidate。三个分支的含义第一个分支count 0表示当前抵消完成需要重新立候选人这是整个算法最重要的入口。第二个分支处理“同党”投票候选人得票加一。第三个分支处理“异党”入场两个元素同归于尽净票数减一。因为题目保证多数存在所以循环结束直接返回candidate。有人会问candidate初始值为什么是 0其实无所谓因为第一次进入循环时count是 0会立刻被覆盖。你写candidate -1也一样只要类型是int就行。3.3 C 语言下容易被忽略的细节C 语言做这道题有几个细节值得单独拎出来说。第一数组元素可能是负数。LeetCode 的数值范围是-10^9到10^9所以不能用“返回 0 表示不存在”这种偷懒写法。如果你要写一个“可能不存在多数”的版本应该用一个独立的found标志或者用一个哨兵机制。千万不要把 0 当作哨兵因为元素本身可能真的是 0。第二count的类型用int足够。numsSize在 LeetCode 上一般不会超过十万级别count最极端也只可能达到numsSize远小于int上限。不需要用long long但也不要声明成unsigned int后又和负数比较那样容易引发类型转换的警告。第三nums理论上可能为空指针。LeetCode 的测试用例不会传空指针但工程代码里必须判空。我一般会在函数开头加一行if (nums NULL || numsSize 0) { return 0; }在实际工程项目中还应该约定错误处理方式而不是直接返回 0。刷题时可以不做但写进简历项目就要谨慎。3.4 如果不保证多数存在怎么改造LeetCode 169 不需要验证但你把代码复用到其他场景时就需要。改造方案很简单第一次遍历只得到candidate第二次遍历重新统计它的次数确认是否真大于n / 2。int majorityElementWithCheck(int* nums, int numsSize) { int candidate 0; int count 0; for (int i 0; i numsSize; i) { if (count 0) { candidate nums[i]; count 1; } else if (nums[i] candidate) { count; } else { count--; } } int verify 0; for (int i 0; i numsSize; i) { if (nums[i] candidate) { verify; } } if (verify numsSize / 2) { return candidate; } return -1; }这个版本适用性更强面试时讲到“如果不存在多数元素”就能直接拿出来。注意返回-1的前提是数组里约定不会出现-1否则会有歧义。LeetCode 虽然用不到但多写一段不亏。4. 我用这几组数据跑了一遍踩了一些坑理论讲完代码也写了接下来分享一些实际跑测试的过程。光看原理容易觉得“这算法怎么这么简单”真正动手之后才会遇到关于直觉和细节的坑。4.1 这几组测试用例最值得跑我建议你在本地跑以下数组观察candidate和count的变化输入数组预期结果为什么要跑[3, 2, 3]3奇数长度多数元素出现在头尾[2, 2, 1, 1, 1, 2, 2]2经典用例大量连续多数元素[1, 2, 3, 2, 2, 2, 1]2多数元素夹在中间[1, 1, 1, 1]1全部相同count 一路累积[1, 2, 1, 3, 1, 4, 1]1多数元素数量刚好过半我跑[1, 2, 1, 3, 1, 4, 1]时输出的过程大约是一开始 1 当选2 把票抵消1 重新当选3 抵消1 再当选4 抵消最后一个 1 当选。最终返回 1。如果不亲手推一遍你很难相信一个看似“东换西换”的过程能准确找出多数元素。4.2 从 O(n) 空间哈希表到 O(1) 空间的实测对比我也试过先写哈希表版本再写摩尔投票版本。哈希表版本在 C 语言里没有现成的容器必须自己维护结构数组typedef struct { int key; int value; } Pair; int majorityElementHash(int* nums, int numsSize) { Pair* table (Pair*)malloc(numsSize * sizeof(Pair)); int size 0; for (int i 0; i numsSize; i) { int found 0; for (int j 0; j size; j) { if (table[j].key nums[i]) { table[j].value; if (table[j].value numsSize / 2) { free(table); return nums[i]; } found 1; break; } } if (!found) { table[size].key nums[i]; table[size].value 1; size; } } free(table); return 0; }这个写法在功能上能跑但你会发现两个问题一是需要动态内存分配多了malloc失败的风险二是内部其实还是数组顺序扫描最坏情况接近 O(n^2)不能算真正的哈希。C 语言没有标准库哈希容器这让哈希解法变得很吃亏。摩尔投票法完全不需要动态内存操作代码量反而更小这是它在 C 语言里最实用的原因。4.3 C 语言做题时的“惯性错误”我见过不少人踩过这几个低级错误这里列出来把count--和count的位置写反。常见原因是没想清楚“遇到不同元素时抵消遇到相同元素时增加支持”。在循环里重新立候选人时忘了把count设为 1结果下一次进入循环时count还是 0导致连续换人。在函数形参里使用sizeof(nums)判断数组长度。注意形参nums是指针sizeof(nums)得到的是指针大小不是数组大小。LeetCode 已经直接给了numsSize不要再自己量。把numsSize误写成n或len这种手滑错误在调试时很浪费时间。4.4 性能误区O(n) 不是只能用一次循环一个常见误解是摩尔投票法要求必须一次遍历完成。实际上 O(n) 时间允许你遍历常数次。比如验证多数是否存在时还要再遍历一遍这仍然是 O(n)。所以面试时完全可以说“先用两次遍历完成验证依然满足线性时间”。LeetCode 169 为了简化直接给了“总是存在”省掉了验证。如果你在面试里主动补上验证步骤反而显得更谨慎因为面试官可能会追问“如果没有多数元素呢”。5. 从 nums[i] 过半到 n/3 的多候选扩展169 本身讲完了但如果只停留在这一道题有点浪费摩尔投票法这个工具。它还有一个非常经典的变形在数组里找出所有出现次数大于 n/3 的元素对应 LeetCode 229。建议你趁热打铁把这个扩展也吃透。5.1 投票法的本质是“对抗性计数”摩尔投票法抽象出来的模式是用一个变量保存当前最有希望存活的元素用一个变量保存该元素相对其他元素的净优势净优势归零就换人。推广到“出现次数大于 n/k”的问题时理论上最多只有 k-1 个候选者。为什么因为如果有 k 个不同元素都出现超过 n/k 次它们的总次数一定超过 n矛盾。这就像比赛名额被“半数”或“三分之一”限制住。过半时最多 1 个赢家超过三分之一时最多 2 个赢家。候选人数固定算法才能做到常数空间。5.2 扩展到众数 II两个候选、两个计数器对 n/3 问题需要维护两个候选人和两个计数器。规则是先看当前数字是否等于 candidate1 或 candidate2是则对应计数器加一。否则看有没有计数器为 0 的位置有就把当前数字放进去。如果两个都非空且都不等于当前数字说明当前数字是“双杀”把两个计数器同时减一。遍历结束后再统计两个候选的真实出现次数把大于 n/3 的加入答案。C 语言参考实现int* majorityElementII(int* nums, int numsSize, int* returnSize) { 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--; } } count1 0; count2 0; for (int i 0; i numsSize; i) { if (nums[i] candidate1) { count1; } if (nums[i] candidate2) { count2; } } int* res (int*)malloc(2 * sizeof(int)); int size 0; if (count1 numsSize / 3) { res[size] candidate1; } if (count2 numsSize / 3) { res[size] candidate2; } *returnSize size; return res; }这段代码里我把candidate2初始值故意设为1是为了避免和candidate1初始同为 0 产生干扰。实际刷 229 时你还可以用类似的思想优化细节但主体流程不变。理解了 169再写 229 的 C 语言版会顺畅很多。5.3 最后的实际经验什么时候不该硬选摩尔投票我个人的体会是摩尔投票法适合“数组可随机访问、只读、一次扫描、空间受限”的场景非常优雅。但它不是万能的。如果你需要统计所有元素的完整频率或者要维护原始顺序哈希表或手动计数器更合适。在 C 语言里如果数据规模很小直接排序取中间值也很快代码可读性最高面试时不容易写错。最后再分享一个小技巧LeetCode 上做这类题先用 C 语言把 O(1) 空间版本写出来再在本地加一行调试打印观察count的变化比盯着题解看十遍都有用。等你哪一天看到任何“过半”或“占三分之一”的题目能立刻想到“这是个投票问题”说明你是真把 169 学透了。