在不创建新列表的情况下以相同顺序打印列表的最大值

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 log 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 log(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实现从用户神智不清莴苣的解决方案在这里.