摩尔投票法可在o(1)空间内找出出现次数>n/2的众数：先通过抵消逻辑确定候选者，再二次遍历验证其频次是否真超半数，缺验证则算法不完整。
为什么不能直接用哈希表统计频次
多数人第一反应是遍历数组，用 std::unordered_map 记每个数出现次数，最后找 > n/2 的那个。这确实能对，但有两处硬伤：额外 O(n) 空间，且最坏要遍历两次（一次计数、一次查结果）。如果题目明确要求“空间复杂度 O(1)”，这条路就走不通。
摩尔投票法：O(1) 空间的核心逻辑
关键观察：若某数字出现次数 > n/2，则它与其他所有数字“抵消”后必然剩余。算法维护一个候选者 candidate 和计数器 count：
- 初始
count = 0，遇到第一个数设为candidate，count = 1 - 后续每遇到一个数：
- 若与
candidate相同，count++ - 若不同，
count--；当count == 0时，用当前数替换candidate，count = 1
- 若与
- 最终
candidate是唯一可能的答案，但必须二次遍历验证其真实频次是否真 > n/2（防止无解数组误出结果）
C++ 实现要点与易错点
注意三个细节：
-
count初始必须为 0，不能为 1 —— 否则首元素强制当选，跳过合理初始化过程 - 验证阶段不能只依赖
candidate存在就返回，必须调用std::count或手写循环确认频次，否则输入{1,2,3}会错误返回3 - 数组为空时需提前处理，避免访问
nums[0]导致未定义行为
简短示例：
int majorityElement(const std::vector<int>& nums) {
int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
// 必须验证
count = 0;
for (int num : nums) if (num == candidate) count++;
return count > nums.size() / 2 ? candidate : -1; // 无解时返回约定值
}</int>
边界情况比想象中多
真正容易翻车的是这些场景：
- 数组长度为偶数（如 4），阈值是 > 2，即至少出现 3 次 —— 不是 ≥ 2
- 存在多个高频数但都不超半（如
{1,1,2,2,3}），此时题目隐含“保证存在解”，但你的代码若没验证步骤，会在这种非法输入下静默返回错误值 - 负数、大整数不影响算法，但若用
int candidate接unsigned int数组，可能符号扩展出问题
验证步骤不是可选项，是安全底线。漏掉它，算法在逻辑上就不完整。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
