#169
简单
低频
投票算法多数元素
这是一道围绕数组展开的高频练习。建议先掌握「投票算法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
给你一个数组，题目保证其中一定存在一个元素，它的出现次数严格超过数组长度的一半。
要求你找出这个元素。
一句话概括：
把不同元素两两抵消，最后剩下来的那个，就是多数元素。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用候选人和计数器做配对抵消，最后留下来的候选值就是多数元素。
推荐代码
推荐解法：投票算法
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 用候选人和计数器做配对抵消，最后留下来的候选值就是多数元素。
class Solution {
public int majorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用 Boyer-Moore 投票算法，线性时间常数空间解决。
核心过程
- 维护一个候选值和一个计数器。
- 计数为 0 时，把当前元素设为新候选人。
- 遇到候选人就加一，遇到其他值就减一，表示配对抵消。
- 因为多数元素超过一半，最后剩下的候选值一定是它。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题最重要的是能把“配对抵消”的直觉讲清楚。
核心思路
多数元素超过一半，意味着它和其他所有元素两两抵消后，仍然会剩下来。Boyer-Moore 投票算法正是把这个抵消过程压成一个候选值和计数器。
步骤讲解
1
计数归零时重置候选人
当计数器为 0，说明当前没有领先候选值，就把当前数字设为新候选人。
为什么这样做：此前元素已经完成抵消，后面的多数元素仍然有机会重新占优。
对应代码提示：if (count == 0) candidate = num;
2
相同加一，不同减一
如果当前数字等于候选人，计数加一；否则计数减一。
为什么这样做：这正对应“多数元素和其他元素配对抵消”的过程。
对应代码提示：count += (num == candidate) ? 1 : -1;
3
遍历结束返回候选人
因为题目保证多数元素一定存在，最后剩下的候选人就是答案。
为什么这样做：多数元素数量超过其余所有元素总和，不可能被完全抵消掉。
对应代码提示：return candidate;
易错点
没理解“超过一半”的前提
如果题目不保证多数元素存在，单次投票结果还需要额外验证。
正确理解：这里可以直接返回，是因为题目已经保证多数元素一定存在。
计数归零时没及时换候选
后续投票就会围绕过期候选值展开，结果不可靠。
正确理解：当
count == 0 时立即把当前数设为新候选人。把它当频次哈希题
哈希表当然能做，但空间不是最优，也错过了这题的经典结论。
正确理解：优先想到 Boyer-Moore 投票算法。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比哈希表统计频次更省空间，是这题最经典的最优解。
适用判断：当题目出现“超过一半”“绝对多数”这类强约束时，优先想到投票算法。
额外提醒
- 投票算法的核心不是统计精确频次，而是做配对抵消。