如何高效获取列表中的前k个较大元素？

Question

什么是解决这个问题最有效、优雅和符合Python风格的方法呢？

给定一个包含n个元素的列表（或者集合，反正就是一堆东西），我们想要找出其中最大的k个元素。（你可以假设k<n/2，这样说也没问题）

举个例子，如果这个列表是：

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

假设n = 9，k = 3。那么，获取这3个最大元素的最有效算法是什么呢？在这种情况下，我们应该得到[9,8,7]，顺序不重要。

谢谢！

曼努埃尔

Answer 1

在编程中，有时候我们会遇到一些问题，比如代码运行不正常或者出现错误。这些问题可能是因为我们写的代码有bug，或者是因为我们没有正确理解某些概念。解决这些问题的第一步就是要仔细检查代码，看看有没有拼写错误、缺少的符号或者不正确的逻辑。

另外，了解你使用的编程语言的基本规则也很重要。每种语言都有自己的语法，就像我们说话时需要遵循语法规则一样。如果不遵循这些规则，代码就会出错。

有时候，查阅一些在线资源，比如StackOverflow，可以帮助我们找到解决方案。那里有很多程序员分享他们的经验和解决问题的方法。通过阅读这些内容，我们可以学到很多实用的技巧，帮助我们更好地编写代码。

总之，遇到问题时不要慌张，先冷静下来，仔细检查代码，必要时寻求帮助。这样，我们就能不断进步，成为更好的程序员。

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

sorted(l)[-k:]

Answer 2

简单来说，O(n log n)的方法就是先把列表排序，然后取最后的 k 个元素。

更合适的方法是使用一种叫做 选择算法，它的运行时间是 O(n + k log k)。

另外，heapq.nlargest 平均需要 O(n log k) 的时间，这个速度可能够用，也可能不够。

（如果 k = O(n)，那么这三种算法的复杂度是一样的（也就是说没必要纠结）。如果 k = O(log n)，那么维基百科上提到的选择算法是 O(n)，而 heapq.nlargest 是 O(n log log n)，不过双对数在大多数实际情况下“足够常数”，所以影响不大。）

Answer 3

使用heapq模块中的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) ]