6

我发现自己经常遇到这个问题：给定一个序列，找到 k 最小的元素。这个问题并不难，但我正在寻找一种既安全又安全的“惯用”方式（很少有地方适合错误）并且可以很好地传达意图。所以最终要做的是对序列进行排序，然后取第一个 k 元素：

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

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

4

3 回答 3

16

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

nth_element是一种部分排序算法，它重新排列 [first, last) 中的元素，使得：

  • 如果 [first, last) 已排序，则 nth 指向的元素将更改为该位置将出现的任何元素。
  • 这个新的第 n 个元素之前的所有元素都小于或等于新的第 n 个元素之后的元素。
于 2012-03-14T15:06:44.357 回答
7

您可能想看看partial_sort()

它既易于理解，也不需要额外的工作，而且sort()如果你只关心第 k 个元素，它会更好[或者至少不会更糟]。

为了获得最佳性能 - 您可能想要使用选择算法，但这需要更多的工作。

于 2012-03-14T15:04:14.823 回答
1

第一种算法：

脚步：

  • 使用选择算法找到第 k_th 元素。
  • 选择它作为枢轴并执行分区（来自快速排序算法），从而将最小的 k 个元素留给枢轴。

复杂性： O(n) 最坏情况

第二种算法：

脚步：

  • 使用make_heap从数组元素中创建堆。
  • 执行 k 次以下操作：

您可以使用优先队列的方法（c'tor、top、pop）来实现相同的效果，而无需知道背后的算法。

复杂度： O(n+ k * log(n)) 最坏情况

于 2016-12-14T19:20:48.543 回答