c++ - 有效地获取 C++ 链表中最大的 3 个整数（未排序）

Question

我听说有一些 std 函数确实给出了数组中最大的 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;
    }
}

Answer 2

也许考虑使用priority_queue.

Answer 3

基本思想是维护一个排序列表、优先级队列或精确N数字堆。您将N列表的第一个值推入其中，然后遍历其余值。如果您遇到大于队列（或其他）中最小值的项目，则删除该元素并将新元素推入。

如果您只是在寻找N=3，那么使用简单的数组可能比优先级队列或其他任何东西更好。您只需进行两次比较即可确定该数组中的哪个元素是最小值。您始终记住最小元素的索引，并且仅在替换它时才更新它。

有趣的是，对于按升序排序的列表，这种方法的性能最差。但是，它本质上仍然是线性时间复杂度。