查找未排序列表的第N项而不排序列表

Question

嘿.我有一个非常大的数组,我想找到第N个最大的值.平凡我可以对数组进行排序,然后取第N个元素,但我只对一个元素感兴趣,所以可能有一个比排序整个数组更好的方法...

Answer 1

堆是这个操作的最佳数据结构,Python有一个很好的内置库来做这个,叫做heapq.

import heapq

def nth_largest(n, iter):
    return heapq.nlargest(n, iter)[-1]

用法示例:

>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920

通过排序确认结果:

>>> list(sorted(iter))[-10]
920

Answer 2

排序至少需要O(nlogn)运行时间 - 有非常有效的选择算法可以在线性时间内解决您的问题.

Partition-based selection(有时Quick select),这是基于快速排序(递归分区)的想法,是一个很好的解决方案(参见伪代码的链接+ 另一个例子).