C++如何在一个数组中寻找出现次数超过一半的数-C++-PHP中文网

boyer-moore投票算法是求多数元素的最优解，因其时间复杂度o(n)、空间复杂度o(1)，利用“超过一半”这一强约束实现抵消逻辑：维护candidate和count，遍历时相等则count++，不等则count--，count为0时更新candidate；题目保证多数元素存在，故无需二次验证。

c++如何在一个数组中寻找出现次数超过一半的数

为什么不能直接用哈希表统计再遍历

多数人第一反应是 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;
}
</int>

std::nth_element 能不能用？性能差异在哪

利用「众数一定在排序后下标为 n/2 的位置」这一事实，有人用 std::nth_element 部分排序，时间复杂度平均 O(n)，最坏 O(n²)，空间 O(1)。但它有硬伤：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

会修改原数组顺序 —— 如果调用方依赖原始顺序，这就是隐蔽 bug
当 n 为偶数时，下标 n/2 对应的是第 (n/2+1) 小的数，恰好是中位数位置，而众数必然等于中位数 —— 这点成立，但前提是数组元素可比较且无歧义；若元素类型重载了 但语义不满足全序（比如浮点 NaN），<code>nth_element 行为未定义
相比投票算法，常数因子更大，实测在小数组上反而更慢

示例写法（仅当允许修改原数组且确定元素可全序比较时）：

int majorityElement(vector<int>& nums) {
    nth_element(nums.begin(), nums.begin() + nums.size()/2, nums.end());
    return nums[nums.size()/2];
}
</int>

边界情况和类型适配要注意什么

投票算法本身不限于 int，但实际使用时容易栽在类型细节上：

数组元素是 long long 或自定义结构体？只要支持 == 和 != 即可，但 candidate 类型必须匹配，不能用 int 存 long long 值
输入是 std::array 或裸指针？算法逻辑不变，但循环需适配迭代器或下标访问
编译器优化级别影响大吗？不影响逻辑，但 count 变量建议声明为 int 而非 size_t —— 因为 count-- 在 size_t 下会绕回极大值，导致死循环