本文介绍了在包含非唯一元素的未排序数组中，选择第k个最大数的最快算法是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
元素的数量可以从100万到1,000万不等。可用于此目的的最快选择算法是什么？请注意，我认为像AVL树这样的数据结构在这里不能工作，因为数组元素重复？可能的重复项：
How to find the kth largest element in an unsorted array of length n in O(n)?
推荐答案
Aselection algorithm可以在O(N)时间内运行。
最常见的方法是遍历数组，保留到目前为止看到的K个最大数。返回该列表的最后一个元素。正如@Chrisa在评论中指出的std::nth_element(文档here)]是使用此方法的最快捷方式。
这篇关于在包含非唯一元素的未排序数组中，选择第k个最大数的最快算法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！
本站部分内容来源互联网,如果有图片或者内容侵犯您的权益请联系我们删除！