algorithm - 是否有“比赛”算法来找到第 k 个最大元素？

Question

我知道我们可以使用“比赛”算法在大小数组中找到第二大元素。现在我想知道我们是否可以使用类似的“比赛”找到第k 个最大的元素。NN+log(N)-2

我知道有一个O(N)“选择”算法可以找到第k 个最大的元素。它Quick Select与“好”枢轴一起使用，可以在O(N). heap我们还可以从数组中构建 aO(N)并从 中检索k元素heap。

我想知道是否有另一种方法。

Answer 1

我相信您可以将其设为 O( N log k ) 算法：迭代数组，并维护迄今为止遇到的最大k个元素的最小堆。所以前k个元素直接进入堆。每个后续元素都将与堆的尖端进行比较，如果它更大，则将从堆中删除尖端并插入新元素，对于大小为k的堆，这是一个 O(log k ) 操作。当算法完成并且序列的长度至少为k时，堆的尖端将具有第k个最大的元素，而堆的其余部分将具有较大的元素。

与中位数 O( n ) 解决方案相比，这种方法的最坏情况行为较差，但对于较小的k将更容易实现并产生相当好的行为。所以它可能非常适合许多实际应用。