摩尔投票法核心是抵消思想：维护候选者与计数器，相同则加一、不同则减一，归零即换人；因多数元素频次严格大于一半，抵消后必剩余，但必须二次遍历验证其真实频次是否超半。
摩尔投票法的核心逻辑是什么
它不是靠统计频次，而是利用「抵消」思想：把众数看作正票，其他数看作负票。只要众数真实存在（且占比 > 50%），最终留下的候选者一定是它——因为正票总数多于所有负票之和，抵消后必有剩余。
关键点在于：算法不验证是否存在众数，只保证「若存在，则一定能被选出」。所以后续必须加一次遍历确认该候选值是否真出现超过一半。
常见错误是直接返回 candidate 而不校验，比如数组 {1,2,3} 会错误返回 3。
怎么写一个安全可用的摩尔投票实现
分两步：第一遍找候选，第二遍计数验证。C++ 中推荐用 std::vector 配合索引遍历，避免迭代器失效或越界。
立即学习“C++免费学习笔记（深入）”；
- 初始化
candidate = nums[0]、count = 1，从下标1开始遍历 - 遇到相同值则
count++，否则count--；当count == 0时，立即用当前元素更新candidate并重置count = 1 - 第二遍必须独立遍历，用
std::count(nums.begin(), nums.end(), candidate)或手写循环，比较结果是否 >nums.size() / 2
示例片段：
int majorityElement(const std::vector<int>& nums) {
int candidate = nums[0], count = 1;
for (size_t i = 1; i < nums.size(); ++i) {
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] == candidate) {
++count;
} else {
--count;
}
}
// 验证环节不可省
int verify = 0;
for (int x : nums) if (x == candidate) ++verify;
return verify > nums.size() / 2 ? candidate : -1; // 无解时返回哨兵值
}
摩尔投票在哪些场景下会失效或需调整
它只适用于「严格超过一半」的众数判定。如果题目改成「出现次数最多的元素（不一定过半）」，就不能直接套用——此时应改用哈希表或 std::sort + 线性扫描。
边界情况要特别注意：
- 空数组：调用前必须检查
nums.empty()，否则nums[0]访问未定义行为 - 类型非
int：泛型版本需用模板，但candidate初始化不能依赖默认构造（如自定义结构体），得用std::optional或额外标志位 - 输入为 C 风格数组：需传入长度参数，不能依赖
sizeof，容易误算
为什么不用 std::unordered_map 统计频次
虽然更直观，但它占 O(n) 额外空间，而摩尔投票是 O(1) 空间、O(n) 时间——在嵌入式或内存受限场景（比如刷 LeetCode 的「空间复杂度 O(1)」要求）中这是硬性门槛。
另外，哈希表平均插入是 O(1)，但存在哈希碰撞导致最坏 O(n) 单次操作；摩尔投票每步都是确定性常数时间，性能更稳定。
不过，如果你正在调试逻辑、不确定数据分布，先写哈希版本快速验证思路，再换摩尔投票优化，是更务实的做法。
