查找未排序列表的第 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屋！