今天的“每日一练”系列，已经走到了第七期。作为一个坚持每天用一道编程题保持手感的老玩家，我越来越觉得这类练习的核心价值，不在于题目本身有多难，而在于你能从一道题里挖出多少东西。第七期我挑了一道很经典的数组题——寻找多数元素（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。 - 如果当前元素等于
candidate，count加 1。 - 如果当前元素不等于
candidate，count减 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]为例：
- 初始：
candidate=1，count=1。 - 遍历到
2，不等于候选者，count减为 0。 - 遍历到
1，此时count==0，把候选者设为1，count=1。 - 遍历到
1，等于候选者，count=2。 - 遍历到
3，不等于候选者，count=1。 - 遍历到
1，等于候选者，count=2。 - 最后返回
1。正确。
这个过程的直觉你还可以这样想：每一对不同的元素都会被“抵消”。多数元素因为数量过半，抵消到最后必然会留下来。所以整个算法其实就是在反复做配对消耗的动作。
3.2 最容易踩的五个坑，我几乎都踩过
第一个坑：从下标 0 开始遍历，导致初始元素被重复计数。如果你把candidate初始化为nums[0]，然后又用for x in nums从头遍历，第一个元素等于candidate，count先加了一，相当于这个元素多算了一次。在某些数据组合下，结果可能没问题，但逻辑上已经不严谨了。所以我的习惯是：初始化后，遍历从nums[1:]开始。
第二个坑：搞混count == 0和count == 1的判断顺序。很多人会先判断x == candidate，再判断count。顺序反了之后，在连续两个不同元素出现时，逻辑会变得混乱。正确顺序一定是先看count是否为 0，如果为 0 就重新选定候选者；然后再看当前元素和候选者是否相等。
第三个坑：忽略“总是存在多数元素”这个条件，强行加验证逻辑。有些同学学得很严谨，会在遍历后加一步验证候选者是否真的是多数元素。如果题目明确说输入一定合法，这步加了也无妨，但会浪费一次 O(n) 遍历。我建议在笔记里统一写成“如果题目不保证存在多数元素，再在末尾遍历一次统计候选者数量”，这样既保证了通用性，又不影响常规场景的性能。
第四个坑：处理n=1的边界用例。只有一个元素时，nums[1:]是空的，直接返回candidate即可，代码天然能处理。但如果你的初始化方式是candidate=None，count=0，然后从头遍历，逻辑会变得复杂。所以最好的做法就是直接把第一个元素作为初始候选者，让边界情况自然被吃掉。
第五个坑：在递归或循环里改动了原数组，导致后续逻辑出错。这个坑更多出现在排序解法里。如果你用了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。遍历数组时：
- 如果当前元素等于
candidate1，count1加 1。 - 如果当前元素等于
candidate2，count2加 1。 - 如果
count1 == 0，把当前元素设为candidate1，count1=1。 - 如果
count2 == 0，把当前元素设为candidate2，count2=1。 - 否则，两个计数器同时减 1，表示当前元素同时抵消了两个候选者各一票。
遍历结束后，还要验证两个候选者是否真的出现超过 n/3 次。因为最多只能有 2 个元素出现次数超过 n/3，所以只需统计这两个候选者的次数即可。
我测试过这个变体，实现比原版复杂一些，但理解原版之后再上手，思路是顺理成章的。它最大的好处是，让你真正理解了“抵消”这个操作和“候选者数量”之间的数学关系：要找超过 n/k 的元素，最多只能有 k-1 个，因此需要维护 k-1 个候选者。这是一个非常优美的推广。
5.2 流式数据场景：不存储全部数据也能找多数派
还有一个延伸场景非常有意思：数据以流的形式源源不断到达，你无法一次性拿到整个数组，也不可能把所有数据都存下来，但你又需要随时知道到目前为止的多数元素是什么。
摩尔投票法在这里就是天然适配的。因为它的所有状态只有candidate和count两个变量，不需要维护历史数据。你每收到一条数据，就按同样的规则更新这两个变量，所以内存占用永远是常量级别的。
我在做一个日志分析工具时，就实际用过这个思路。当时需要在超大日志文件里快速找出占比最高的错误码，文件大到不可能一次性读进内存。我用了类似摩尔投票的方法做了一次流式扫描，内存占用只有几十字节，速度也非常快。后来虽然因为业务需求变化改成了更精确的统计方案，但那次实际应用让我对投票法的价值有了很深的认可。
5.3 聊聊投票法背后更普适的思想
如果你已经吃透了摩尔投票法，你会发现它背后的核心思想，其实是一种“多数派对抗少数派”的博弈模型。这种思想在很多地方都有影子。
比如在分布式系统里，讨论“多数派决策”时，本质上就是在寻找一个在任何分区下都能被多数节点支持的值。又比如在数据处理链路里，当你需要对流式数据进行“去重后找主要类型”时，投票法的变体也经常能派上用场。
我不太建议为了用算法而用算法。但如果你能养成一个习惯——每学到一个新算法，就想想“这个算法的核心假设是什么？这个假设在同等条件下还能解决哪些问题？”——那你的学习效率会远远超过单纯刷题的阶段。
写在最后，我个人实操中的一点体会
第七期写到这里，我复盘了这个月的刷题过程。相比刚开始做每日一练的那几天，我现在最大的变化不是代码写得快了，而是拿到一道题之后，第一反应不再是“怎么AC”，而是“这题的边界条件是什么，有没有更优的解法思路，这个思路还能不能泛化到别的题型”。这个转变，就是每天多花十五分钟把题目拆透彻、把解法挨个比较一遍换来的。
如果你也想从这个系列里获得最大的收益，我给你一个特别实用的建议：准备一个专门的笔记文件，每道题记录三样东西——第一，你的第一版解法是什么；第二，最优解的核心思路和复杂度；第三，这道题让你联想到的其他题目或场景。坚持一个月之后，你再回头翻翻这些笔记，会发现自己已经形成了一条完整的知识网络，而不是一盘散沙。第七期就到这，我继续去准备第八期了。
