关于是否存在最优雅的求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 Inputsn = 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 heapq import nlargest
    ll = [i for i in range(10, 1000)]
    print(nlargest(3, ll))

# [999, 998, 997]