关于是否存在最优雅的求TOP N 问题的方法？

Question

最近在搞算法，其中遇到最经典的问题求一个数组前N大的问题。我的方法比较野蛮，没有参考价值，是利用python的sorted 函数排序,对排好序的数组提取最后的N 个数就是TOP N 了。

def solve(l):

  l = sorted(l)

  i = 1

  while i <=4:

print l[n-i]

i = i + 1

# Getting Inputs

n = input()

l = []

for line in range(n):

l.append(input())

solve(l)

有人知道比较优秀的处理是怎么样子吗？

Answer 1

这时候用Heap很优雅，但是时间复杂度依然是O(nlogn)。当top-k中k很小的时候（k<logn）每次找到最大并记录实际上是最快的，时间复杂度是O(kn)。其他的你可以参考Selection Algorithm，时间复杂度也是O(n)级别。

Answer 2

from&nbsp;heapq&nbsp;import&nbsp;nlargest &nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;=&nbsp;[i&nbsp;for&nbsp;i&nbsp;in&nbsp;range(10,&nbsp;1000)] &nbsp;&nbsp;&nbsp;&nbsp;print(nlargest(3,&nbsp;ll))#&nbsp;[999, 998, 997]