Aja*_*mos 0 c c++ selection
可能重复: 如何在O(n)中找到长度为n的未排序数组中的第k个最大元素？
元素的数量可以在1到1千万之间变化.这是最快的选择算法吗？请注意我认为由于数组元素的重复,像AVL Trees这样的数据结构在这里不起作用？
Jef*_*ter 6
甲选择算法可以在O(N)时间运行.
最常见的方法是通过数组,保持你目前为止看到的K个最大数字.返回该列表的最后一个元素.正如@ChrisA在评论中指出的std::nth_element(这里记录)是使用这种方法的最快方法.
std::nth_element
如果您总是想要最大的第K个项(并且有时会更改数据),那么请考虑将数据存储在堆中.这样更昂贵,但会为您提供数据的"实时"结构.
归档时间：
13 年，2 月 前
查看次数：
1716 次
最近记录：