查找未排序列表的第 N 项而不对列表进行排序 [英] Finding Nth item of unsorted list without sorting the list
问题描述
嘿.我有一个非常大的数组,我想找到第 N 个最大值.简单地说,我可以对数组进行排序,然后取第 N 个元素,但我只对一个元素感兴趣,所以可能有比对整个数组排序更好的方法......
Hey. I have a very large array and I want to find the Nth largest value. Trivially I can sort the array and then take the Nth element but I'm only interested in one element so there's probably a better way than sorting the entire array...
推荐答案
排序至少需要 O(nlogn) 运行时间 - 有非常高效的 选择算法 可以在线性时间内解决您的问题.
Sorting would require O(nlogn) runtime at minimum - There are very efficient selection algorithms which can solve your problem in linear time.
Partition-based selection
(有时是Quick select
),它基于quicksort(递归分区)的思想,是一个很好的解决方案(伪代码+另一个例子).
Partition-based selection
(sometimes Quick select
), which is based on the idea of quicksort (recursive partitioning), is a good solution (see link for pseudocode + Another example).
这篇关于查找未排序列表的第 N 项而不对列表进行排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!