如何有效地獲得python中列表中的k個更大的元素

解決這個問題的最高效，最優雅和最可靠的方法是什麼？如何有效地獲得python中列表中的k個更大的元素

給出n個元素的列表（或集合或其他），我們希望得到k個最大的元素。（你可以假定k<n/2不失一般性，我猜）例如，如果列表是：

l = [9,1,6,4,2,8,3,7,5]

N = 9，並假設K = 3 什麼是用於檢索的3最有效的算法最大的？在這種情況下，我們應該得到[9,8,7]，沒有特別的順序。

謝謝！從heapq模塊曼努埃爾

來源

2010-02-11 Manuel Aráoz

+1現在基本目的被服務了，高爾夫球？ – 2010-02-11 10:41:52

使用nlargest

from heapq import nlargest 
lst = [9,1,6,4,2,8,3,7,5] 
nlargest(3, lst) # Gives [9,8,7]

你也可以給一個關鍵的情況下nlargest你想改變你的標準：

from heapq import nlargest 
tags = [ ("python", 30), ("ruby", 25), ("c++", 50), ("lisp", 20) ] 
nlargest(2, tags, key=lambda e:e[1]) # Gives [ ("c++", 50), ("python", 30) ]

來源

2010-02-11 09:50:45 sharjeel

+1：我不知道abt這個模塊...謝謝 – mshsayem 2010-02-11 09:55:59

偉大的語言排名:)） – 2016-01-17 11:57:18

l = [9,1,6,4,2,8,3,7,5] 

sorted(l)[-k:]

來源

2010-02-11 09:50:14 mshsayem

這比我的更好） – Rorick 2010-02-11 09:53:41

...但它不適用於k == 0的特定情況。 :) – EOL 2010-02-11 10:27:58

可以使用heapq模塊。

>>> from heapq import heapify, nlargest 
>>> l = [9,1,6,4,2,8,3,7,5] 
>>> heapify(l) 
>>> nlargest(3, l) 
[9, 8, 7] 
>>>

來源

2010-02-11 09:50:47 sykora

我們不需要heapify它在這裏 – garg10may 2015-10-13 07:22:46

sorted(l, reverse=True)[:k]

來源

2010-02-11 09:52:31 Rorick

簡單，爲O（n log n）的方式是對列表進行排序，然後得到最後ķ元素。

正確的方法是使用selection algorithm，它運行在O（n + k log k）時間。

另外，heapq.nlargesttakes O(n log k) time，這可能會或可能不夠好。如果k = O（n），那麼所有3種算法都具有相同的複雜性（即不打擾），如果k = 0（log n），則維基百科中描述的選擇算法是O（n ）和heapq.nlargest是O（n log log n），但是對於大多數實際來說，雙對數是「足夠恆定的」，這與它無關緊要。）

來源

2010-02-11 09:56:12 kennytm

如何有效地獲得python中列表中的k個更大的元素

回答

相關問題