c++ - 使用 STL 容器查找序列的 k 个最大元素的最快算法是什么

Question

我需要使用 c++ 任何 STL 容器找到序列的 k 最大元素的最快算法。我的想法:使用列表或 vector ，对它们进行排序，获取前 k 个元素。在这种情况下，操作数等于 n*log(n)。 n - 元素数。但我认为这不是最好的。

Answer 1

使用 std::partial_sort 的方法可能是最好的答案。

另请注意 std::nth_element，只是获取第 n 个位置右侧的元素(并将序列划分为“更小的” ' 在第 n 个元素之前和之后 '更大'

因此，如果您真的对前 k 个元素感兴趣(没有特定的内部顺序)，那么 nth_element 绝对需要 cookies