LeetCode 169. 多数元素
目录
题目描述
题意分析
给定长度为
n的数组，返回其中出现次数严格超过⌊n / 2⌋的那个元素。「超过一半」是一个非常强的条件：这个元素比其余所有元素加起来还多。这意味着答案是唯一的——不可能有两个元素同时超过一半。
题目还明确承诺「数组总是存在多数元素」。这个前提很关键：它意味着我们只需要「找出可能的答案」，而不需要「验证它确实是答案」。如果没有这条保证，任何只扫一遍就下结论的做法都必须补一次验证。
边界方面：
n可以为 1（单元素自己就是多数元素）；元素可以是负数，所以不能拿元素值本身当计数器的哨兵。
解法：Boyer-Moore 投票法
核心思路
问题关键：多数元素出现次数超过一半，比其他所有元素的总数还多。每次抵消一对不同元素，都不会改变最终的多数元素。
Boyer-Moore 投票法用
candidate表示当前候选，count表示候选尚未被抵消的净票数。遇到相同元素加一，遇到不同元素减一；票数归零时，已处理前缀可以完全抵消，下一个元素重新成为候选。不变量：处理完任意前缀后，删去已配对的不同元素，未抵消部分只包含
count个candidate。由于真正的多数元素无法被其他元素全部抵消，题目又保证它存在，最终候选必然是答案。哈希计数也能做到 $O(n)$ 时间，但需要 $O(n)$ 空间。
解题步骤
- 初始化
count = 0；candidate的初值不重要。- 遍历元素：若
count == 0，先把当前元素设为候选。- 当前元素等于候选就
count++，否则count--。- 遍历结束返回候选。题目保证多数元素存在，因此无需第二次计数验证。
例如
[2,2,1,1,1,2,2]的净票数依次为1,2,1,0,1,0,1，最终候选为2。
代码实现
class Solution {
public int majorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
}
func majorityElement(nums []int) int {
candidate := 0
count := 0
for _, num := range nums {
if count == 0 {
candidate = num
}
if num == candidate {
count++
} else {
count--
}
}
return candidate
}
复杂度分析
- 时间复杂度：$O(n)$，只遍历一次数组。
- 空间复杂度：$O(1)$，只维护候选和净票数。
关键点总结
count是未抵消的净票数，不是候选的真实出现次数。- 抵消一对不同元素后，多数元素在剩余元素中仍占多数，这是正确性的核心。
- 若题目不保证多数元素存在，必须再遍历一次，验证候选出现次数是否大于
n / 2。
易错点总结
count == 0的判断放在增减票之后：[1,2,2]会错过正确的换候选时机。- 把
count当作真实次数：[2,1,2,1,2]最终count = 1，但2实际出现 3 次。- 用
candidate == 0判断是否有候选：数组元素可以为0或负数，只能看count。- 忽略题目保证：对
[1,2,3]，算法仍会给出候选，但它不是多数元素；无保证时必须复验。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 229. 多数元素 II | 中等 | 投票法推广到超过 n / 3，双候选且必须二次验证 |
| 剑指 Offer 39. 数组中出现次数超过一半的数字 | 简单 | 同题异面，练习口述抵消不变量 |
| 面试题 17.10. 主要元素 | 简单 | 不保证多数存在，投票后必须补一次计数验证 |