5

我有一个包含n 个双精度值的列表，我需要在该列表中找到k个最低双精度值

  • k远小于n
  • 具有n 个双精度值的初始列表是随机排序的
  • 不需要对找到的k个最低 double 值进行排序

你会推荐什么算法？

目前我使用Quicksort对整个列表进行排序，然后从排序列表中取出前k个元素。我希望应该有一个更快的算法。

谢谢您的帮助！！！

4

5 回答 5

10

您可以为解决方案建模以匹配Python 标准库中的 nlargest() 代码。

  • 将前k个值堆放在一个 maxheap 上。
  • 迭代剩余的n - k 个值。
  • 将每个元素与堆顶元素进行比较。
  • 如果新值较低，请执行heapreplace操作（将最顶部的堆元素替换为新值，然后向下筛选）。

该算法可能非常有效。例如，当 n=100,000 且 k=100 时，对于随机排列的输入，比较次数通常约为 106,000。这仅比 100,000 次多一点的比较来找到单个最小值。而且，它在整个数据集上进行的比较比完整的快速排序少了大约 20 倍。

各种算法的相对强度研究总结在：http ://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest

于 2012-07-10T05:55:44.153 回答
8

您可以使用选择算法找到第 k 个最低元素，然后迭代并返回它以及低于它的所有元素。如果列表可以包含重复项，则必须做更多的工作（确保您最终不会得到更多需要的元素）。
这个解决方案是O(n)。选择算法在 C++ 中实现为nth_element()

另一种选择是使用大小为 的最大堆k，并在保持堆容纳所有 k 个最小元素的同时迭代元素。

for each element x:
   if (heap.size() < k):
      heap.add(x)
   else if x < heap.max():
      heap.pop()
      heap.add(x)

完成后 - 堆包含 k 个最小元素。
这个解决方案是O(nlogk)

于 2012-07-10T05:30:01.723 回答
2

看看C++ 标准库中的partial_sort算法。

于 2012-07-10T05:31:16.143 回答
2

您可以使用std::nth_element。这是 O(N) 复杂度，因为它不对元素进行排序，它只是将它们排列为使得某个 N 下的每个元素都小于 N。

于 2012-07-10T05:32:05.427 回答
0

您可以使用选择排序，它需要 O(n) 来选择第一个最小值。一旦我们在位置 1 上设置了这个最低值，我们就可以重新扫描数据集以找出第二个最低值。并且可以做到这一点，直到我们有第 k 个最低值。这样，如果 k 足够小然后 n 那么我们将有复杂度 kn 相当于 O(n)...

于 2012-07-10T11:35:35.690 回答