在Python中不使用heapq或排序查找数组前k个元素

Question

我想在Python中找到一个列表里前k个最大的元素，但不想用heapq或者对列表进行排序。

这是我尝试的代码，

list = [20,4,67,22,445,1,34]
k = 3
newList=[]

for i in range(0,k):
    newList.append(list[i])
for i in list:
    mini = min(newList)
    if i <= mini:
        continue
    else:
        newList.remove(mini)
        newList.append(i)
print newList

但是我得到的结果是67, 67, 445。我哪里出错了呢？

Answer 1

hughdbrown 提出的解决方案有一个我注意到的错误。如果列表中有相似的项，那么结果只会显示其中一个。例如，如果列表是 [1, 2, 3, 4, 5, 5]，那么结果会显示 [3, 4, 5]，而不是 [4, 5, 5]。

Answer 2

你在新列表一开始就有67这个数字，而且67这个数字一直没有被移除。

Answer 3

你可以简单地这样做：

a = [20,4,67,22,445,1,34]
k = 3
newList=[]

for i in range(k):
    pos = a.index(max(a))
    newList.append(a[pos])
    a.pop(pos)

>>> print newList
[67, 445, 34]

Answer 4

这个问题在你添加一些跟踪信息后就很明显了：

>>> list = [20,4,67,22,445,1,34]
>>> k = 3
>>> newList=[]
>>> 
>>> for i in range(0,k):
...     newList.append(list[i])
... 
>>> for i in list:
...     mini = min(newList)
...     if i <= mini:
...         continue
...     else:
...         print newList
...         print "Replacing {0} with {1}".format(mini, i)
...         newList.remove(mini)
...         newList.append(i)
...         print newList
...         print '-' * 20
... 
[20, 4, 67]
Replacing 4 with 20
[20, 67, 20]
--------------------
[20, 67, 20]
Replacing 20 with 67
[67, 20, 67]
--------------------
[67, 20, 67]
Replacing 20 with 22
[67, 67, 22]
--------------------
[67, 67, 22]
Replacing 22 with 445
[67, 67, 445]

当你遍历这个列表并第二次添加67的时候，实际上列表里已经有67了。

我会把它改写成：

>>> numbers = [20,4,67,22,445,1,34]
>>> k = 3
>>> newList = numbers[:k]
>>> 
>>> for i in numbers[k:]:
...     mini = min(newList)
...     if i > mini:
...         print "Replacing {0} with {1}".format(mini, i)
...         newList.remove(mini)
...         newList.append(i)
... 
Replacing 4 with 22
Replacing 20 with 445
Replacing 22 with 34
>>> print newList
[67, 445, 34]

不过，我建议你不要把你的列表命名为 list。