c++ - “Best”(惯用的)方法，从C++中的容器中选择k个最小的元素

This question already has answers here:

Retrieving the top 100 numbers from one hundred million of numbers

(12个答案)


4年前关闭。




我经常遇到这个问题:给定一个序列，找到k个最小的元素。这个问题并不难，但是我正在寻找的是一种“惯用的”方法，既安全又安全(很少出现这种情况)。错误)，并且可以很好地传达意图。所以最终要做的是对序列进行排序，然后取第一个k元素:

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

在我看来，这既安全又易于理解，但是这里的复杂度是nlogn + k，而不仅仅是n。
你们是怎么做到的，有没有一种惯用的方式(可能使用了一些晦涩的功能)，可以在无需重新实现轮子的情况下提供最佳的复杂性

最佳答案

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

关于c++ - “Best”(惯用的)方法，从C++中的容器中选择k个最小的元素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9704478/