c++ - 高效获取 C++ 链表中最大的 3 个整数(未排序)

Question

我听说有一些标准函数确实给出了数组的最大 n 个整数，但是链表怎么样？

我认为解决方案是使用几个 for 循环遍历链表，但似乎 C++ 库中可能有更简单的解决方案。

谢谢。

Answer 1

如果你不能使用其他数据结构，我会这样做:

typedef std::list<int> IntList;
InstList list = <your_values>;

int top[3];
for (size_t i = 0; i < 3; i++)
    top[i] = std::numeric_limits<int>::min();

IntList::iterator it, end;
for (it = list.begin(), end = list.end(); it != end; ++it) {
    const int& value = *it;
    if (value > top[2]) {
        top[0] = top[1];
        top[1] = top[2];
        top[2] = value;
    } else if (value > top[1]) {
        top[0] = top[1];
        top[1] = value;
    } else if (value > top[0]) {
        top[0] = value;
    }
}