如何从包含n个数字的列表中找出前k个最大的数字（假设n>k）？

Question

我正在寻找一些Python代码，可以从一个未排序的n个数字列表中返回k个最大的数字。我最初想通过先对列表进行排序来实现这一点，但这可能会变得非常笨重。

例如，我想要从中查找k个最大数字的列表名为list1。

> list1 = [0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]

这里n = 7，如果k = 3，也就是说如果我要从一个由7个数字组成的列表中找到最大的3个数字，那么输出应该是0.5, 0.7, 0.5。

如何实现？

- Lokesh

---

最优的算法返回长度为n的数组中前k个值是什么？ - pablochan

我想要 Python 的代码。其他链接是 C 语言的。 - Lokesh

不，他提供的链接中没有一行代码，只有要遵循的步骤。你可以轻松地将其转换为Python。 - Anthony Teisseire

这个过程对我来说似乎很难跟进，因为我是新手，对编程和Python不太熟悉。我想知道是否有一种使用max函数的方法可以直接得到我想要的输出。此外，我正在参加一个编程比赛，受限制不能创建自己的函数 :( - Lokesh

在这种情况下，向SO询问实际代码而不是指针将是作弊... - Steve Barnes

我没有作弊。确切的问题并不是我要问的。它只是一个可以帮助我构建代码的部分。 - Lokesh

Answer 1

Python拥有所有电池包含在内 - 使用heapq模块 :)

from heapq import nlargest

data = [0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]
print nlargest(3, data)

它比对整个数组进行排序更快，因为它使用了部分堆排序。

- Roman Pekar

---

这是一个更好的解决方案。花了我大约一年的时间才想出来。 - Lokesh

如果您对指数感兴趣，可以使用“key”参数。nlargest(3, range(len(data)), key=lambda idx: data[idx])。 - Oren

Answer 2

可以这样做：

>>> list1
[0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]
>>> list2 = list1[:] #make a copy of list1
>>> k = 3
>>> result = []
>>> for i in range(k):
        result.append(max(list2)) #append largest element to list of results
        list2.remove(max(list2)) # remove largest element from old list
>>> result
[0.7, 0.5, 0.5]
>>> 

- Pawel Miech

Answer 3

假设您不想修改list1，您可以创建一个排序的副本：

In [1]: list1 = [0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]

In [2]: list2 = sorted(list1)

In [3]: list2
Out[3]: [0.3, 0.3, 0.3, 0.4, 0.5, 0.5, 0.7]

在list2中，最大的数是最后的数，因此我们将使用切片：

In [4]: list2[-3:]
Out[4]: [0.5, 0.5, 0.7]

我添加的链接指向Python的文档。作为一个初学者，你应该先看一下教程，然后你最需要的是库参考，因为丰富的标准库是Python如此优美的其中之一。

- Roland Smith

---

非常感谢。这正是我正在寻找的东西。我一直在努力对列表进行排序，而实际上已经有一个很好的sorted(list1)函数了。再次感谢！！！ - Lokesh

Answer 4

另一个解决方案：

另外一个方案：

import numpy as np
k = 3
ind = np.argpartition(list1, -k)[-k:] # index of the k highest elements
print(list1[ind])

- Fernando S. Peregrino

---

我很欣赏这个答案，因为我认为它所需的时间应该比其他解决方案要少（虽然我没有与其他人严格地“计时”）。现在，一个附属问题：可以按最高指数先排序，其次是次高指数，依此类推吗？ - Partha D.

Answer 5

不使用排序，采用贪心算法

k_largest = list1[:k]
for num in list1:
    for c in range(k):
        if num > k_largest[c]:
            k_largest = k_largest[:c] + [num] + k_largest[c:-1]  # maintains sorted order
            break
print(k_largest)

- davegrays