C++如何查找数组中的第二大元素-C++-PHP中文网

找第二大元素应采用单次扫描o(n)算法，用first和second维护最大与第二大值，初始化为llong_min，更新时需避免重复最大值，最后检查second是否仍为llong_min以判断是否存在有效第二大。

c++如何查找数组中的第二大元素

直接遍历一次就能搞定，别用排序

排序整个数组再取倒数第二个元素，时间复杂度是 O(n log n)，纯属浪费。找第二大元素本质是“单次扫描中的状态维护”，O(n) 就够了——关键是初始化和更新逻辑要稳。

常见错误是把初始值设成 INT_MIN 然后直接比较，结果数组全为负数时出错；或者没处理重复最大值（比如 [5,5,4,3] 的第二大是 4，不是 5）。

用两个变量 first 和 second 分别存最大、第二大，初始都设为 LLONG_MIN（比 int 更安全）
遍历每个元素 x：若 x > first，则 second = first; first = x;；否则若 x > second && x != first，才更新 second
最后检查 second 是否仍为 LLONG_MIN，是说明不存在有效第二大（如数组长度

用 `std::nth_element` 必须小心边界

std::nth_element 看似省事，但它只保证第 n 个位置放对元素，前面无序、后面也无序。想拿第二大，得调用两次或配合 std::unique，反而容易翻车。

比如对 vector<int> v = {3,1,4,1,5}</int>，执行 std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>())</int> 后，v[1] 是第二大值（4），但前提是数组去重过——否则重复最大值会挤占位置。

必须先用 std::sort + std::unique 或手写去重逻辑，否则 [5,5,5,4] 调 nth_element 可能返回 5
nth_element 不改变原数组相对顺序，但你根本不需要这个特性，还多一层风险
它平均 O(n)，但最坏 O(n²)，而手写遍历是稳定 O(n)

处理重复值和边界情况的实际写法

真实业务里，输入不总是理想整数数组：可能为空、单元素、全相同、含 INT_MAX。硬编码 INT_MIN 当哨兵会崩。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

下面这段代码覆盖了多数坑：

long long findSecondLargest(const vector<int>& arr) {
    if (arr.size()  first) {
            second = first;
            first = x;
        } else if (x > second && x != first) {
            second = x;
        }
    }
    return second == LLONG_MIN ? LLONG_MIN : second;
}</int>

返回 LLONG_MIN 表示无效（调用方需判断），比抛异常更轻量
用 long long 避免 INT_MAX 更新 first 后，second 溢出
x != first 这个判断不能省，否则 [1,1,1] 会让 second 错误地变成 1

如果必须用标准库，`std::set` 最省心但有代价

对小数组或不关心性能的场景，std::set 自动去重+有序，取倒数第二个迭代器最直白：

set<int> s(arr.begin(), arr.end());
if (s.size() 
<p>但要注意：<code>std::set</code> 插入是 <code>O(n log n)</code>，空间额外 <code>O(n)</code>，且无法保留原始数组索引信息。如果后续还要用原数组下标，这套就废了。</p>
<p>真正麻烦的是——有人用 <code>std::priority_queue</code>，结果写成 <code>priority_queue<int></int></code> 然后 pop 两次，忘了重复值问题，pop 出来还是同一个数。</p></int>