This question already has answers here:
Retrieving the top 100 numbers from one hundred million of numbers
(12个答案)
4年前关闭。
我经常遇到这个问题:给定一个序列,找到k个最小的元素。这个问题并不难,但是我正在寻找的是一种“惯用的”方法,既安全又安全(很少出现这种情况)。错误),并且可以很好地传达意图。所以最终要做的是对序列进行排序,然后取第一个k元素:
在我看来,这既安全又易于理解,但是这里的复杂度是nlogn + k,而不仅仅是n。
你们是怎么做到的,有没有一种惯用的方式(可能使用了一些晦涩的功能),可以在无需重新实现轮子的情况下提供最佳的复杂性
(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/
10-16 04:53