LeetCode 169 · 多数元素：Boyer-Moore 投票算法，最优雅的 O(1) 空间解法
这道题最有趣的地方不在于答案本身，而在于那个 O(1) 空间的解法——Boyer-Moore 投票算法。第一次看到的时候我愣了好一会儿：不需要哈希表、不需要排序、不需要分治，就两个变量，扫一遍就能找到出现超过一半的元素？是的，而且原理极其巧妙。
题目长什么样
给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。
输入：nums = [2,2,1,1,1,2,2]
输出：2
说人话就是：数组里一定有一个元素出现次数超过一半，把它找出来。题目保证这个元素一定存在，所以不需要处理"没有多数元素"的情况。
"超过一半"这个条件非常强——它意味着多数元素的数量比所有其他元素加起来还多。正是这个性质让 Boyer-Moore 算法成为可能。
第一反应：哈希表计数
最直接的想法——遍历一遍，用哈希表统计每个元素出现的次数，然后找最大的。
fromcollectionsimportCounterclassSolutionHash:defmajorityElement(self,nums:List[int])->int:counts=Counter(nums)returnmax(counts,key=counts.get)| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n) | 遍历一遍 + 查找最大值 |
| 空间 | O(n) | 最坏情况每个元素都不同 |
时间已经是最优了，但空间不行。题目进阶要求 O(1) 空间，哈希表显然不满足。
利用排序：中位数一定是多数元素
因为多数元素超过一半，所以排序后位于中间位置的元素一定是多数元素——不管多数元素怎么分布，它一定覆盖中点。
classSolutionSort:defmajorityElement(self,nums:List[int])->int:nums.sort()returnnums[len(nums)//2]| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n log n) | 排序的代价 |
| 空间 | O(1) | 原地排序 |
空间满足了，但时间退步了。能不能两全其美？
最优解：Boyer-Moore 投票算法
这是这道题的精髓。思路可以用一句话概括：不同阵营互相抵消，最后剩下的一定是多数元素。
怎么理解"投票"
把数组想象成一场选举：
- 每个数字代表一个"候选人"
- 遍历数组就像逐个人投票
- 我们维护一个"候选人"和一个"计数器"
- 遇到同阵营的（相同的数字），计数器 +1
- 遇到不同阵营的（不同的数字），计数器 -1
- 计数器归零时，换一个新的候选人
classSolution:defmajorityElement(self,nums:List[int])->int:count=0candidate=Nonefornuminnums:ifcount==0:candidate=num count+=(1ifnum==candidateelse-1)returncandidate为什么这一定能找到多数元素？
关键推理：
多数元素的数量 > n/2，其他所有元素加起来 < n/2。 即使最坏情况——所有非多数元素都和多数元素抵消： 抵消掉的多数元素数量 = 非多数元素总数 < n/2 剩余的多数元素数量 = 多数元素总数 - 抵消掉的数量 > n/2 - n/2 = 0 所以多数元素永远不会被完全抵消，最后剩下的一定是它。跑一遍示例 2
nums = [2, 2, 1, 1, 1, 2, 2] i=0: num=2, count=0 → 候选人设为 2, count=1 i=1: num=2, 2=2 → 同阵营! count=2 i=2: num=1, 1≠2 → 不同阵营! count=1 i=3: num=1, 1≠2 → 不同阵营! count=0 ← 归零了！ i=4: num=1, count=0 → 候选人换为 1, count=1 i=5: num=2, 2≠1 → 不同阵营! count=0 ← 又归零了！ i=6: num=2, count=0 → 候选人换为 2, count=1 最终候选人 = 2 ✓注意中间候选人从 2 变成了 1，但最后又变回了 2。这就是"抵消"的过程——虽然中间状态看起来不对，但最终结果一定是正确的，因为多数元素的数量优势保证它不会被完全消灭。
再跑一个更直观的例子
nums = [2, 2, 2, 2, 1, 1, 1] i=0: num=2, count=0 → 候选人=2, count=1 i=1: num=2, 同阵营 → count=2 i=2: num=2, 同阵营 → count=3 i=3: num=2, 同阵营 → count=4 i=4: num=1, 不同阵营 → count=3 i=5: num=1, 不同阵营 → count=2 i=6: num=1, 不同阵营 → count=1 最终候选人 = 2 ✓ (2 出现 4 次，1 出现 3 次)这个例子更清楚——多数元素从头到尾都是候选人，其他元素只是不断消耗计数器，但始终没能把 count 减到 0。
三种解法放在一起看
| 解法 | 时间 | 空间 | 一句话评价 |
|---|---|---|---|
| 哈希表计数 | O(n) | O(n) | 最直观，面试保底 |
| 排序取中位数 | O(n log n) | O(1) | 利用了排序后中点必是多数元素的性质 |
| Boyer-Moore 投票 | O(n) | O(1) | 最优解，两个变量扫一遍 |
这道题教会我什么
"超过一半"是一个极强的条件
多数元素的数量比其他所有元素加起来还多。这个"数量优势"让它能在任何形式的"对抗"中存活。Boyer-Moore 本质上就是在模拟这种对抗——多数元素和不属于它的元素互相消耗，多数元素永远不会被耗尽。
这个思路可以推广：如果某个东西的数量严格超过总量的一半，那它一定能经受住任何"成对抵消"。
最好的算法往往不需要额外数据结构
哈希表是万能的，但它不是免费的——O(n) 的空间不是小事。Boyer-Moore 告诉我们，有时候问题本身的数学性质已经蕴含了答案，不需要"暴力"地记录所有信息。只需要抓住最核心的不变量（多数元素不会被完全抵消），两个变量就足够了。
代码短不代表思路简单
Boyer-Moore 的代码只有 6 行，但背后的数学推理一点都不简单。面试时如果被问到这道题，光写出代码不够——你得能解释"为什么 count 归零时可以放心换候选人"。如果解释不清楚，面试官会认为你是背的而不是理解的。
完整测试代码
fromtypingimportListclassSolution:defmajorityElement(self,nums:List[int])->int:count=0candidate=Nonefornuminnums:ifcount==0:candidate=num count+=(1ifnum==candidateelse-1)returncandidateclassSolutionSort:defmajorityElement(self,nums:List[int])->int:nums.sort()returnnums[len(nums)//2]classSolutionHash:defmajorityElement(self,nums:List[int])->int:fromcollectionsimportCounter counts=Counter(nums)returnmax(counts,key=counts.get)if__name__=="__main__":s=Solution()nums=[3,2,3]print(f"输入:{nums}, 输出:{s.majorityElement(nums)}")nums=[2,2,1,1,1,2,2]print(f"输入:{nums}, 输出:{s.majorityElement(nums)}")nums=[1]print(f"输入:{nums}, 输出:{s.majorityElement(nums)}")nums=[6,5,5]print(f"输入:{nums}, 输出:{s.majorityElement(nums)}")nums=[2,2,2,2,1,1,1]print(f"输入:{nums}, 输出:{s.majorityElement(nums)}")相关题目推荐：
- LeetCode 229 · 求众数 II（超过
⌊n/3⌋的元素，Boyer-Moore 的扩展版，维护两个候选人）- LeetCode 1150 · 检查一个数是否在数组中占绝大多数（有序数组中验证多数元素）