亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

關于是否存在最優雅的求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條經驗 獲得超6個贊

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

# [999, 998, 997]


查看完整回答
反對 回復 2018-07-18
  • 2 回答
  • 0 關注
  • 564 瀏覽

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號