发现未分类的列表的第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.

基于分区的选择（有时快速选择），这是基于快速排序的思想（递归分割），是一个很好的解决方案（见链接伪code + 另一个例子）。

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屋！