在C++中从容器中选择k个最小元素的"最佳"(惯用)方法

Question

我经常发现自己遇到这个问题:给定一个序列,找到k-最小的元素.问题并不那么难,但我正在寻找的是一种"习惯性"的方式来做到这一点既安全又很少错误)并且沟通意图很好.所以最终做的是对序列进行排序,然后取第一个k元素:

std::sort(container.begin(),container.end());
std::vector<T> k_smallest(container.begin(),container.begin() + k);

在我看来这既安全又易于理解,但这里的复杂性是nlogn + k,而不仅仅是n.你们是如何做到这一点的,是否有一种自觉的方式(使用一些模糊的功能)可以提供最佳的复杂性而无需重新实现轮子

Answer 1

std :: nth_element() - 平均线性复杂度.

nth_element 是一种部分排序算法,它重新排列[first,last]中的元素,这样:

如果[first,last]被排序,则nth指向的元素将更改为该位置中将出现的任何元素.

在这个新的第n个元素之前的所有元素都小于或等于新的第n个元素之后的元素.

@GreyGeek:在使用`std :: nth_element`之后,所有_less_而不是nth的元素都在[begin,nth]范围内,它们只是没有被排序.如果您需要它们,您可以对该子范围进行排序. (3认同)
但是,如果你需要对它们进行排序,你应该使用`partial_sort`来开始. (3认同)
+1令人惊讶的是,我们一般认为使用的STL算法很少! (2认同)

Answer 2

你可能想看看partial_sort()

它既易于理解,也不需要额外的工作,sort()如果你只关心第k个元素,那么预期会更好[或者至少不会更差] .

为获得最佳性能 - 您可能希望使用选择算法,但需要更多工作.