今天的“每日一练”系列已经走到了第七期。作为一个坚持每天用一道编程题保持手感的老玩家我越来越觉得这类练习的核心价值不在于题目本身有多难而在于你能从一道题里挖出多少东西。第七期我挑了一道很经典的数组题——寻找多数元素Majority Element题目不难但它的解法跨度非常大从暴力枚举、哈希表、排序到分治再到摩尔投票法几乎覆盖了算法入门阶段遇到的大部分核心思想。这篇文章不是单纯贴个答案就完事。我会带你把这题拆透从题目设计、考点分析、三种解法逐步演进到摩尔投票法的完整实现细节、最常见的五个坑、以及这类算法思想还能怎么迁移到别的场景。不管你是刚开始刷题的新手还是已经积累了一些经验的同学这一期应该都有值得你带走的东西。1. 题目拆解与考点分析先搞懂“多数元素”在问什么1.1 题目长什么样边界条件先想清楚原题很精简给定一个大小为 n 的数组找到其中的多数元素。多数元素是指在数组中出现次数大于 n/2 的元素。假设数组非空并且给定的数组总是存在多数元素。举个例子输入[3, 2, 3]输出3输入[2, 2, 1, 1, 1, 2, 2]输出2。数据规模一般在10^4到10^5量级这在任何主流在线评测系统里都意味着O(n²) 的暴力算法大概率能过但完全不是这道题想考察的东西。我对所有带“总是存在”这类前置条件的题目都很敏感。它本质上是在告诉你你的算法不需要处理“没有多数元素”的异常分支可以放心大胆设计针对性解法。但题目“总是存在多数元素”并不代表你可以不做边界检查。n 1时数组里只有一个元素它本身就算多数元素。很多同学在写摩尔投票法时初始值选错或者循环从i 1开始跳过了第一个元素在这个边界用例上就会翻车。1.2 为什么这道题能成为热门题这道题之所以被各大题库收录并且在面试里被反复考察不是因为答案有多难而是它的解法梯度实在太完整了。你可以用最朴素的双重循环也可以写出哈希表一行统计代码还可以用排序后取中位数的技巧更可以用时间复杂度 O(n)、空间复杂度 O(1) 的摩尔投票法一步到位。每一种解法背后代表了一种典型的算法思想。暴力循环对应“枚举法”哈希表对应“空间换时间”排序取中对应“利用题目特性的巧妙一瞥”分治对应“大问题拆小问题”摩尔投票则是对“抵消”这个概念最直观的应用。一个题目能同时覆盖这么多知识点作为每日一练的素材再合适不过。在实际工程里“找出超过半数的元素”也不是一个纯理论问题。比如日志分析中找出占比过半的错误码、在线投票系统中判断某个选项是否获得绝对多数这类场景本质上就是在求解多数元素。所以别觉得这是纯粹刷题用的小把戏理解它的解法演进过程对培养解决实际问题的直觉很有帮助。2. 五种解法审视从暴力到摩尔投票一路优化到底2.1 暴力解法能跑通但不是这题的目的暴力解法是我一直提倡“先想出来再说”的那个起点。思路很直白遍历数组中的每一个元素再遍历一遍数组统计它出现了多少次遇到第一个出现次数大于 n/2 的元素直接返回。写成代码特别简单嵌套两层循环时间复杂度 O(n²)def majority_element_brute(nums): n len(nums) for i in range(n): count 0 for j in range(n): if nums[j] nums[i]: count 1 if count n // 2: return nums[i] return -1但你看一眼就知道一旦数组规模超过 10^4这个算法就开始吃力了。我建议初学者在纸上画一遍流程最多跑一个长度为 6 的小数组确认逻辑没写错就够了。暴力解法的价值是帮你建立“最直接的思考路径”但它绝对不能作为你的最终答案更不能让你觉得“题目不过如此”。2.2 哈希表解法空间换时间的标准套路暴力解法慢在“每次都要重新统计”。能不能遍历一遍就记住每个元素出现的次数哈希表天然就是干这个的。用一个字典存元素和频次边遍历边统计发现某个元素的次数超过了 n/2立即返回。def majority_element_hash(nums): n len(nums) freq {} for x in nums: freq[x] freq.get(x, 0) 1 if freq[x] n // 2: return x return -1代码比暴力版本清爽太多。时间复杂度 O(n)空间复杂度 O(n)。这里有一个性能细节值得注意freq.get(x, 0)在 Python 里比if x not in freq的写法更高效因为少了一次哈希查找的额外开销。你如果在打比赛或做性能敏感项目这种细微差别还是值得在意的。哈希表的缺点是显而易见的如果数组有 10 万个元素你就要额外开一个最多能存 10 万条记录的字典。空间开销在某些嵌入式环境或者内存受限的场景下是不可接受的。这时候就需要不用额外空间的算法——排序法和摩尔投票法。2.3 排序取中利用数学特性的巧妙解法这道题有一个隐藏的数学特性如果某个元素出现的次数大于 n/2那么把数组排序之后这个元素一定会出现在数组的中间位置。原因很简单出现次数过半的元素无论怎么分布排序后必然会覆盖中间位置的下标。def majority_element_sort(nums): nums.sort() return nums[len(nums) // 2]这个解法代码最短但有两个缺点。第一它改变了原数组如果后续流程还需要原数据顺序你就得先拷贝一份第二排序的复杂度是 O(n log n)在数据量大的时候还是比 O(n) 慢一个量级。我拿它当教学例子讲给学生时主要想说明一件事在动手写代码之前先想想题目有没有特殊的数学性质。这种“多想一想”的习惯往往能把一个普通题变成送分题。2.4 分治解法从经典套路里找感觉分治的思路是把数组分成左右两半分别递归找出左半部分的多数元素和右半部分的多数元素。如果两边返回的多数元素相同那这个数一定是整个数组的多数元素如果不同那就分别统计这两个数在整个数组里出现的次数谁次数多谁是答案。用代码写出来大概是这个样子def majority_element_divide(nums, left, right): if left right: return nums[left] mid (left right) // 2 left_major majority_element_divide(nums, left, mid) right_major majority_element_divide(nums, mid 1, right) if left_major right_major: return left_major left_count sum(1 for i in range(left, right 1) if nums[i] left_major) right_count sum(1 for i in range(left, right 1) if nums[i] right_major) return left_major if left_count right_count else right_major分治的好处是逻辑清晰、思路优雅时间复杂度 O(n log n)。但实现起来需要处理递归边界还要在合并阶段做一次区间内统计代码细节明显多不少。在实际面试中如果你能在白板上写出分治版本并解释清楚复杂度已经能体现出不错的功底了。但说实话——它并不是最优解。2.5 摩尔投票法空间复杂度压到 O(1) 的最优解前面所有方法都用了额外存储或者排序而摩尔投票法能同时做到时间 O(n)、空间 O(1)。这个算法的核心思想用一个生活场景最容易解释想象有一个房间里面有很多人投票选“多数派”。两个不同阵营的人一旦相遇就互相抵消、一起离开房间。最后留在房间里的那个人就是多数派。具体执行方式特别简单维护一个候选者变量candidate和一个计数器count。初始时candidate可以设为nums[0]count为 1。然后从第二个元素开始遍历如果count 0就把当前元素设为新的候选者count设为 1。如果当前元素等于candidatecount加 1。如果当前元素不等于candidatecount减 1。遍历结束后candidate就是我们要找的多数元素。这个算法的正确性建立在“多数元素存在”这个前置条件上。因为多数元素出现的次数超过了所有其他元素出现次数之和所以无论怎样抵消它都会剩下正数数量留在最后。这就是它空间复杂度能做到 O(1) 的数学根基。五种解法从 O(n²) 一路优化到 O(n)这本身就是一节非常好的复杂度分析课。我每次做每日一练特地把这些解法都梳理一遍价值不只是“会做一道题”而是真正理解“怎么选算法”。3. 实操过程与核心细节把摩尔投票法写成可复用的代码3.1 摩尔投票法的标准实现每一步都讲清楚为什么在看代码之前我想先强调一个容易被忽略的点遍历一定要从数组的第二个元素开始而不是从第一个。因为我们已经把第一个元素当作初始候选者了如果再从它开始遍历等于把它多统计一次会导致计数出现偏差。下面是标准实现def majority_element(nums): candidate nums[0] count 1 for x in nums[1:]: if count 0: candidate x count 1 elif x candidate: count 1 else: count - 1 return candidate我拿一个数组手动走一遍确保你彻底理解。以[1, 2, 1, 1, 3, 1]为例初始candidate1count1。遍历到2不等于候选者count减为 0。遍历到1此时count0把候选者设为1count1。遍历到1等于候选者count2。遍历到3不等于候选者count1。遍历到1等于候选者count2。最后返回1。正确。这个过程的直觉你还可以这样想每一对不同的元素都会被“抵消”。多数元素因为数量过半抵消到最后必然会留下来。所以整个算法其实就是在反复做配对消耗的动作。3.2 最容易踩的五个坑我几乎都踩过第一个坑从下标 0 开始遍历导致初始元素被重复计数。如果你把candidate初始化为nums[0]然后又用for x in nums从头遍历第一个元素等于candidatecount先加了一相当于这个元素多算了一次。在某些数据组合下结果可能没问题但逻辑上已经不严谨了。所以我的习惯是初始化后遍历从nums[1:]开始。第二个坑搞混count 0和count 1的判断顺序。很多人会先判断x candidate再判断count。顺序反了之后在连续两个不同元素出现时逻辑会变得混乱。正确顺序一定是先看count是否为 0如果为 0 就重新选定候选者然后再看当前元素和候选者是否相等。第三个坑忽略“总是存在多数元素”这个条件强行加验证逻辑。有些同学学得很严谨会在遍历后加一步验证候选者是否真的是多数元素。如果题目明确说输入一定合法这步加了也无妨但会浪费一次 O(n) 遍历。我建议在笔记里统一写成“如果题目不保证存在多数元素再在末尾遍历一次统计候选者数量”这样既保证了通用性又不影响常规场景的性能。第四个坑处理n1的边界用例。只有一个元素时nums[1:]是空的直接返回candidate即可代码天然能处理。但如果你的初始化方式是candidateNonecount0然后从头遍历逻辑会变得复杂。所以最好的做法就是直接把第一个元素作为初始候选者让边界情况自然被吃掉。第五个坑在递归或循环里改动了原数组导致后续逻辑出错。这个坑更多出现在排序解法里。如果你用了nums.sort()然后取中间元素原数组顺序已经被打乱了。后续如果再对数组做其他判断很容易拿到错误结果。3.3 边界条件测试写代码前先在脑子里跑用例我每次写完这种简单算法都会在提交前先做一轮“心理测试”。测试用例我一般覆盖这五种普通情况[1, 2, 3, 2, 2]多数元素是2。只有一个元素[5]返回5。元素的分布集中在开头[3, 3, 3, 3, 1, 2]返回3。元素的分布集中在结尾[1, 2, 3, 3, 3, 3]返回3。所有元素都相同[1, 1, 1, 1]返回1。这五组用例跑通之后代码基本不会有问题。写单元测试的时候也可以把这几个场景固化成测试函数方便以后复用。4. 常见问题与排查技巧实录这七期打卡以来我收到了很多读者私信。大家的问题集中在几个点上我统一回复一下。4.1 “这道题暴力都能过为什么我还要学摩尔投票法”这可能是最常被问到的问题。在数据量小的时候暴力解法的确能过甚至比花里胡哨的最优解跑得更快——因为算法本身的常数开销极小。但刷题和做工程的差距就在这里在生产环境里数据规模是你无法预料的。一枚日志文件可能有上亿行一次网络请求的字段可能有几十万个。到那个量级O(n²) 和 O(n) 的差距是天文数字。摩尔投票法的价值不在于“过题”而在于它让你见识到存在一种算法既不需要额外空间也不需要排序靠一个精妙的数学性质就能在线性时间内解决问题。这种思维模式比题目本身值钱得多。4.2 “如果没有‘总是存在多数元素’这个条件摩尔投票法会怎样”这是一个极好的问题。答案是它可能返回一个“不是多数元素”的候选者。比如数组[1, 2, 3, 4]没有元素出现次数超过一半。算法会一路抵消最后返回的候选者是4但它显然不是多数元素。所以如果题目没有保证输入合法你需要加一次验证步骤。实现方法很简单在投票结束后再遍历一次数组统计candidate的出现次数看是否大于n/2。验证步骤的时间复杂度同样是 O(n)整体还是 O(n)只是常数翻一倍。我一般在工程代码里会保留这步宁可多一次遍历也不愿返回错误结果。4.3 “每天练一道题但是总感觉忘得很快怎么办”这是我从第一期开始就反复强调的问题刷题不复习等于白刷。我自己的做法是每周挑一道曾经做过的题重新写一遍解法而且刻意要求自己不要打开上次的代码凭记忆和理解从头写起。这样下来遗忘速度会明显变慢。另外一个心得是不要追求一天刷好几道而是把一道题吃透。比如今天这道题如果你能亲手写出五种解法并且能解释清楚每种解法的复杂度来源和适用场景那这题给你带来的提升超过刷十道没走心的题。5. 从一道题看一类题摩尔投票法还能用到哪里5.1 从“超过一半”扩展到“超过三分之一”既然摩尔投票法能找绝对多数元素那它能不能找“出现次数超过 n/3”的元素答案是能而且这是这道题最经典的一道变体。思路从“一组候选者对抗”升级成“两组候选者同时对抗”。具体做法是维护两个候选者candidate1、candidate2和两个计数器count1、count2。遍历数组时如果当前元素等于candidate1count1加 1。如果当前元素等于candidate2count2加 1。如果count1 0把当前元素设为candidate1count11。如果count2 0把当前元素设为candidate2count21。否则两个计数器同时减 1表示当前元素同时抵消了两个候选者各一票。遍历结束后还要验证两个候选者是否真的出现超过 n/3 次。因为最多只能有 2 个元素出现次数超过 n/3所以只需统计这两个候选者的次数即可。我测试过这个变体实现比原版复杂一些但理解原版之后再上手思路是顺理成章的。它最大的好处是让你真正理解了“抵消”这个操作和“候选者数量”之间的数学关系要找超过 n/k 的元素最多只能有 k-1 个因此需要维护 k-1 个候选者。这是一个非常优美的推广。5.2 流式数据场景不存储全部数据也能找多数派还有一个延伸场景非常有意思数据以流的形式源源不断到达你无法一次性拿到整个数组也不可能把所有数据都存下来但你又需要随时知道到目前为止的多数元素是什么。摩尔投票法在这里就是天然适配的。因为它的所有状态只有candidate和count两个变量不需要维护历史数据。你每收到一条数据就按同样的规则更新这两个变量所以内存占用永远是常量级别的。我在做一个日志分析工具时就实际用过这个思路。当时需要在超大日志文件里快速找出占比最高的错误码文件大到不可能一次性读进内存。我用了类似摩尔投票的方法做了一次流式扫描内存占用只有几十字节速度也非常快。后来虽然因为业务需求变化改成了更精确的统计方案但那次实际应用让我对投票法的价值有了很深的认可。5.3 聊聊投票法背后更普适的思想如果你已经吃透了摩尔投票法你会发现它背后的核心思想其实是一种“多数派对抗少数派”的博弈模型。这种思想在很多地方都有影子。比如在分布式系统里讨论“多数派决策”时本质上就是在寻找一个在任何分区下都能被多数节点支持的值。又比如在数据处理链路里当你需要对流式数据进行“去重后找主要类型”时投票法的变体也经常能派上用场。我不太建议为了用算法而用算法。但如果你能养成一个习惯——每学到一个新算法就想想“这个算法的核心假设是什么这个假设在同等条件下还能解决哪些问题”——那你的学习效率会远远超过单纯刷题的阶段。写在最后我个人实操中的一点体会第七期写到这里我复盘了这个月的刷题过程。相比刚开始做每日一练的那几天我现在最大的变化不是代码写得快了而是拿到一道题之后第一反应不再是“怎么AC”而是“这题的边界条件是什么有没有更优的解法思路这个思路还能不能泛化到别的题型”。这个转变就是每天多花十五分钟把题目拆透彻、把解法挨个比较一遍换来的。如果你也想从这个系列里获得最大的收益我给你一个特别实用的建议准备一个专门的笔记文件每道题记录三样东西——第一你的第一版解法是什么第二最优解的核心思路和复杂度第三这道题让你联想到的其他题目或场景。坚持一个月之后你再回头翻翻这些笔记会发现自己已经形成了一条完整的知识网络而不是一盘散沙。第七期就到这我继续去准备第八期了。
