arrays - 如何在一次迭代中找到数组中的第二个最大元素？

Question

我需要一次迭代中未排序数组中的第二大元素。 例如:数组是 3 9 8 2 0 -4 87 45 3 2 1 0 答案应该是45，在一次迭代中找到最大元素很简单，但是如何在同一次迭代中找到第二个最大值，或者在数组的fort迭代后的恒定时间。

Answer 1

int sz = arr.size();
assert(sz >= 2);
int maxElem = arr[0];
int secElem = arr[1];
if (maxElem < secElem) swap(maxElem, secElem);

for (int i = 2; i < sz; ++i) {
    if (arr[i] > maxElem) {
        secElem = maxElem;
        maxElem = arr[i];
    } else if (arr[i] == maxElem) {
        secElem = maxElem;
    } else if (arr[i] < maxElem && arr[i] > secElem)) {
        secElem = arr[i];
    }
}