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

timlentse 发布于 2014/11/14 10:22
阅读 372
收藏 1

最近在搞算法,其中遇到最经典的问题求一个数组前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)

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

加载中
0
Jeky
Jeky

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

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

elmar_chen
elmar_chen
用heap的复杂度是nlogk,不是nlogn吧
timlentse
timlentse
thanks
0
domicc
domicc
堆排序 维护大小为N的堆
0
elmar_chen
elmar_chen
http://en.wikipedia.org/wiki/Binary_heap
0
库特
库特
from heapq import nlargest
    ll = [i for i in range(10, 1000)]
    print(nlargest(3, ll))

# [999, 998, 997]


0
一刀
一刀

《算法导论》中的方案:

https://github.com/yidao620c/core-algorithm/blob/master/ch02_sort/at210_imin_list.py

返回顶部
顶部