从长度为N的数组返回前k个值的最佳算法

从长度为N的数组返回前k个值的最佳算法

方法一

由于k很小，因此您可以使用锦标赛方法找到第k个最大值。Knuth的《编程艺术》，第3卷，第212页中介绍了此方法。

首先在n-k +
2个元素上创建一个锦标赛。像淘汰赛网球比赛。首先，将您分成两对，并比较两对的成员（好像这两对进行了比赛而一个输了）。然后，获胜者将再次分成几对，依此类推，直到您获得获胜者为止。您可以将其视为一棵树，获奖者位于顶部。

这需要精确进行n-k + 1次比较。

现在，这些n-k + 2的赢家不能成为您的第k个最大元素。考虑它在比赛中的路径P。

现在从剩余的k-2中选择一个，然后沿着路径P前进，这将为您带来新的最大值。基本上，您可以用k-2元素之一替换以前的获胜者，从而重做锦标赛。令P为新赢家的道路。现在从k-3中选择另一个，然后沿着新路径前进，依此类推。

在用尽k-2的最后，将最大的替换为-infinity，而锦标赛中最大的将成为第k大。您扔掉的元素是前k-1个元素。

这最多需要进行

n - k + (k-1) [log (n-k+2)]

比较才能找到前k个。虽然它使用O（n）内存。

就比较次数而言，这可能会击败任何选择算法。

方法2

或者，您可以保持k个元素的最小堆。

首先插入k个元素。然后，对于数组的每个元素，如果它小于堆的min元素，则将其丢弃。否则，删除-min堆并从数组中插入元素。

最后，堆将包含前k个元素。这需要

O(n log k)

比较。

当然，如果n小，仅对数组进行排序就足够了。代码也会更简单。