什么是使用stl-containers查找序列的k-maximal元素的最快算法

Question

我需要使用c ++任何stl-containers来查找序列的k-maximal元素的最快算法. 我的想法:使用列表或向量,对它们进行排序,获得第一个k元素.在这种情况下,操作数等于n*log(n).n - 元素数量.但我认为这不是最好的.

Answer 1

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

还要注意std::nth_element哪个只是在第n个位置得到元素(并将序列分成'之前'较小'和'较大'之后第n个元素

因此,如果你真的只对前k个元素感兴趣(没有特别的内部排序)那么nth_element肯定需要饼干

Answer 2

假设随机未排序的数据，我认为最快的是创建一个排序的链表，循环遍历原始容器，并且对于每个元素，如果它大于结果向量中的最低值，则将其挂钩（在正确的排序位置）。如果列表现在包含更多，则 k 个元素将删除最低值。

最坏情况（已排序的原始容器）意味着O(k*n)最好情况O(n)。