在包含非唯一元素的未排序数组中，选择第k个最大数的最快算法是什么？

可能的重复项：
How to find the kth largest element in an unsorted array of length n in O(n)?

元素的数量可以从100万到1,000万不等。可用于此目的的最快选择算法是什么？请注意，我认为像AVL树这样的数据结构在这里不能工作，因为数组元素重复？

---

解决方案

Aselection algorithm可以在O(N)时间内运行。

最常见的方法是遍历数组，保留到目前为止看到的K个最大数。返回该列表的最后一个元素。正如@Chrisa在评论中指出的std::nth_element(文档here)]是使用此方法的最快捷方式。

如果您总是想要前第k个最大的项(数据有时会更改)，那么可以考虑将数据存储在heap中。这样做的成本较高，但为您提供了数据的"实时"结构。