为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

沧海一幻觉 2018-07-17 13:20:44
最近在搞算法,其中遇到最经典的问题求一个数组前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)有人知道比较优秀的处理是怎么样子吗?
查看完整描述

2 回答

?
www说

TA贡献1775条经验 获得超8个赞

这时候用Heap很优雅,但是时间复杂度依然是O(nlogn)。当top-k中k很小的时候(k<logn)每次找到最大并记录实际上是最快的,时间复杂度是O(kn)。

其他的你可以参考Selection Algorithm,时间复杂度也是O(n)级别。


查看完整回答
反对 回复 2018-07-18
?
梦里花落0921

TA贡献1772条经验 获得超5个赞

from heapq import nlargest
    ll = [i for i in range(10, 1000)]
    print(nlargest(3, ll))

# [999, 998, 997]


查看完整回答
反对 回复 2018-07-18
  • 2 回答
  • 0 关注
  • 511 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信