Boyer-Moore投票算法是求多数元素的最优解，因其时间复杂度O(n)、空间复杂度O(1)，利用“超过一半”这一强约束实现抵消逻辑：维护candidate和count，遍历时相等则count++，不等则count--，count为0时更新candidate；题目保证多数元素存在，故无需二次验证。
为什么不能直接用哈希表统计再遍历
多数人第一反应是 std::unordered_map 计数，再扫一遍找频次 > n/2 的元素——逻辑没错，但空间复杂度 O(n)，而题目隐含要求最优解。实际面试或算法题中，这个限制常被默认：只允许 O(1) 额外空间。更关键的是，它忽略了「超过一半」这个强约束带来的数学性质：众数必然存在且唯一，且能被 Boyer-Moore 投票算法 在一次遍历中锁定。
Boyer-Moore 投票算法怎么写才不出错
核心是维护一个候选者 candidate 和计数器 count，遍历时：相同则 count++，不同则 count--；count 归零就换候选者。但容易漏掉两个关键检查点：
- 输入数组为空时，
candidate未初始化，直接返回会 UB —— 必须先判空 - 算法只保证「若众数存在，则最终
candidate是它」，但不验证存在性 —— 题目说「出现次数超过一半」，意味着众数一定存在，所以省略二次验证可接受；但如果题干改成「可能不存在」，就必须额外遍历一次确认candidate实际频次 -
count初始化必须为 0，不能为 1 —— 否则第一个元素永远被强行设为候选，破坏抵消逻辑
标准实现：
int majorityElement(vector<int>& nums) {
if (nums.empty()) return 0; // 或抛异常
int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
std::nth_element 能不能用？性能差异在哪
利用「众数一定在排序后下标为 n/2 的位置」这一事实，有人用 std::nth_element 部分排序，时间复杂度平均 O(n)，最坏 O(n²)，空间 O(1)。但它有硬伤：
立即学习“C++免费学习笔记（深入）”；
- 会修改原数组顺序 —— 如果调用方依赖原始顺序，这就是隐蔽 bug
- 当 n 为偶数时，下标
n/2对应的是第 (n/2+1) 小的数，恰好是中位数位置，而众数必然等于中位数 —— 这点成立，但前提是数组元素可比较且无歧义；若元素类型重载了<但语义不满足全序（比如浮点 NaN），nth_element行为未定义 - 相比投票算法，常数因子更大，实测在小数组上反而更慢
示例写法（仅当允许修改原数组且确定元素可全序比较时）：
int majorityElement(vector<int>& nums) {
nth_element(nums.begin(), nums.begin() + nums.size()/2, nums.end());
return nums[nums.size()/2];
}
边界情况和类型适配要注意什么
投票算法本身不限于 int，但实际使用时容易栽在类型细节上：
- 数组元素是
long long或自定义结构体？只要支持==和!=即可，但candidate类型必须匹配，不能用int存long long值 - 输入是
std::array或裸指针？算法逻辑不变，但循环需适配迭代器或下标访问 - 编译器优化级别影响大吗？不影响逻辑，但
count变量建议声明为int而非size_t—— 因为count--在size_t下会绕回极大值，导致死循环
真正麻烦的是数据来源不可信：比如从网络读入的数组长度字段被篡改，导致实际元素数远小于声称的 n，此时 nums.size()/2 计算中位数位置就失效。投票算法对此鲁棒性更高——它只依赖真实元素个数。
