按相同顺序打印列表的最大值，而不创建新列表

Question

这是我的清单

[9,1,2,11,8]

我需要打印这个列表中的前3个，

[9,11,8]

很容易对顶值进行排序和获取，并遍历相同的复制列表以按给定顺序找到顶值，但我不应该使用新列表来完成此任务。这有可能吗？

Answer 1

def k_largest(iterable, k=3):
    it = iter(iterable)
    result = [next(it) for _ in range(k)] # O(k) space
    r_min = min(result)
    for elem in it:
        if elem > r_min:
            result.remove(r_min)  # O(n*k) time
            result.append(elem)
            r_min = min(result)
    return result

在平局的情况下，第一个值获胜。如果您希望最后一个值获胜，只需将>更改为>=即可。

对于大数据和小选择来说，这是一种很好的方法，即n >> k，其中n是输入的长度，k是选择的数字。在这种情况下，k项不重要，因此该方法的时间复杂度为O(n)，有利于基于排序的方法的O( n )。如果k很大，这将不再是一个好的解决方案。您应该考虑维护已排序的结果集，将其一分为二以进行插入，也许还可以使用quickselect来查找最大值。

另一种选择是使用Python stdlib的heapq.nlargest，它的代码更简单，尽管在实践中它通常会更慢：

import heapq
from operator import itemgetter

def k_largest_heap(iterable, k=3):
    ks = heapq.nlargest(k, enumerate(iterable), key=itemgetter(1))
    return [k for i, k in sorted(ks)]

我认为这是O(n (K))，尽管不可否认，我在这里已经达到了我的知识的边缘。

具有10,000个整数列表的一些计时：

from random import randint
nums =  [randint(1, 10000) for _ in range(10000)]
%timeit k_largest(nums)
# 331 µs ± 4.69 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit k_largest_heap(nums)
# 1.79 ms ± 27.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit top_three(nums)
# 1.39 ms ± 16.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

注意：top_three实现是来自user Delirious Lettuce here的解决方案。

Answer 2

我会修改一个select-sort来捕获(n)为MAX，而不是只捕获一个。而不是运行n2，只需遍历列表一次。

所以9,1,2,11,8

你可以用一个MAX列表0,0,0初始化，然后遍历你的列表，取出比MAX更大的东西

1. 9,0,0
2. 9,1,0
3. 9,1,2
4. 9,11,2

最棘手的部分是步骤4，您需要决定保留9和2，并用11替换1。

Answer 3

你也可以为你的list实现一个包装类。对于列表中的最大值，拥有私有数据成员(在您的示例中为3)。在执行插入和删除时更新这些变量。