LeetCode 169. 多数元素
题目描述
题意分析
给定一个非空整数数组，返回其中出现次数严格大于
n / 2的元素，其中n为数组长度。这里要求超过总数的一半，比“出现次数最多”更强；符合条件的值最多只有一个。题目保证多数元素一定存在，因此不需要处理不存在的情况。进阶要求只遍历线性次数并使用常量额外空间，不能依靠为每种值分别存储计数来满足这个空间要求。
解法：Boyer-Moore 投票法
核心思路
[!blue]
关键性质是：每次删去一对值不同的元素，不会改变真正的多数元素。设它出现
m次，且m > n / 2。若删去的一对中包含它，剩余次数为m - 1，仍大于(n - 2) / 2；若一对都不是它，它的次数不变，只会占据更高比例。因此，只要持续抵消不同元素，多数元素就不可能被完全抵消。不必真的删除数组元素，用
candidate和count模拟这个过程。处理完任意前缀后，把已抵消的不同元素对忽略，剩余部分可以表示成count个candidate。读到与候选相同的值就增加一票；读到不同的值，就用它抵消一个候选，减少一票。当
count == 0时，说明此前已处理的元素全部配对抵消，没有留下候选。当前元素成为新候选，并且自身也要计入一票。因此代码先检查是否需要换候选，再统一执行相同加一、不同减一。遍历结束，所有未抵消元素都等于最终候选。由于真正的多数元素不会被完全抵消，这个候选就只能是它。
count表示剩余票数，不等于该值在原数组中的真实出现次数；本题能直接返回候选，依赖的是“多数元素一定存在”的保证。
解题步骤
- 初始化
count = 0；candidate的初值不重要。- 遍历元素：若
count == 0，先把当前元素设为候选。- 当前元素等于候选就
count++，否则count--。- 遍历结束返回候选。由于题目保证多数元素存在，无需再次统计其出现次数。
代码实现
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)$，只维护候选和净票数。
关键点总结
[!green]
count是未抵消的净票数，不是候选的真实出现次数。- 抵消一对不同元素后，多数元素在剩余元素中仍占多数，这是正确性的核心。
- 若题目不保证多数元素存在，必须再遍历一次，验证候选出现次数是否大于
n / 2。
易错点总结
[!yellow]
- 切换候选时忘记给当前元素计票，会丢掉这个元素；本实现先在
count == 0时换候选，再执行本轮加减票。- 把
count当作真实出现次数，再用它判断是否超过一半，会把正确候选错误排除；它只是抵消后的剩余数量。- 用
candidate == 0判断是否有候选不可靠，因为0和负数也可以是合法元素，应看count是否为零。- 把这段代码用于不保证多数元素存在的问题时，不能直接返回候选，还必须重新计数并确认其出现次数严格超过一半。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 17.10. 主要元素 | 简单 | 本题保证多数元素存在，原题可能不存在，所以投票后还需再次统计验证。 |
| 229. 多数元素 II | 中等 | 阈值降为三分之一后，最多有两个候选，需要扩展抵消规则。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！