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

Which is the fastest algorthm for selecting kth largest number in an unsorted array containing non -unique elements?(在包含非唯一元素的未排序数组中,选择第k个最大数的最快算法是什么?)

本文介绍了在包含非唯一元素的未排序数组中,选择第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中。这样做的成本较高,但为您提供了数据的"实时"结构。

这篇关于在包含非唯一元素的未排序数组中,选择第k个最大数的最快算法是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:在包含非唯一元素的未排序数组中,选择第k个最大数的最快算法是什么?

基础教程推荐