LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字
题目描述
题意分析
找到数组中出现次数严格超过长度一半的数字，并返回这个数值。题目保证这种数字存在，因此数组非空，且答案最多只有一个；“超过一半”不包含刚好一半。
同一个值的出现位置可以分散，不要求连续。需要比较的是它的总次数与其余所有数字次数之和，而不是寻找最长连续段。
解法：Boyer-Moore 投票
核心思路
[!blue]
假设真正的多数元素为
x，它的数量大于所有其他元素数量之和。从数组中移除一对不同值时，如果其中一个是x，双方各减一，x的数量优势不变；如果两个都不是x，其他元素减少两个，优势反而更大。因此不断抵消异值对，不会消除真正的多数元素。用
candidate保存尚未抵消的候选值，count保存该值剩余的未抵消数量。每轮开始时，已经读过的前缀可以看成若干被删除的异值对，加上count个相同的候选值。读到同值时加一，将它并入剩余候选；读到异值时减一，相当于把新值与一个候选配对删除。若
count已为零，说明此前前缀已经全部配对抵消，下一项可以成为新候选，并且必须计入这一票。上述操作始终只删除不同值的配对。由于真正的多数元素不可能被全部抵消，扫描完成后剩余的候选就一定是它。
count只是抵消后的数量，不是真实频次；当前题目有存在性保证才可直接返回候选，若取消这项保证，则需再统计候选的实际次数。
解题步骤
- 初始化
count = 0，此时还没有有效候选，candidate的初值不参与判断。- 从左到右读取当前数，若
count == 0，先将它设为新候选。- 当前数等于候选时加一，否则减一；更换候选后也执行这一判断，确保当前票不遗漏。
- 扫描结束后，按题目保证返回
candidate。
代码实现
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是候选在抵消后的净票数，不是候选的真实出现次数。- 换候选后仍要处理当前这一票，所以“判零”和“加减票”是两个连续判断。
易错点总结
[!yellow]
- 换候选后仍要计入当前票，不能把后面的加减票判断写成与判零互斥的
else if。- 若采用首元素为候选且
count = 1的初始化，遍历就必须从第二个元素开始，避免首元素计算两次。count是配对删除后剩余的数量，不能拿它当候选在原数组中的实际出现次数。- 本题保证多数存在；取消保证后，投票只能筛出候选，必须二次计数判断是否真的超过一半。
- 多数元素无需连续出现，按连续段长判断无法求出总次数上的多数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 17.10. 主要元素 | 简单 | 本题保证多数元素存在，原题可能不存在，所以投票后还需再次统计验证。 |
| 229. 多数元素 II | 中等 | 阈值降为三分之一后，最多有两个候选，需要扩展抵消规则。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！