如何返回另一个列表中3个最低值的列表

Question

如何返回另一个列表中3个最低值的列表。例如，我想获得此列表的3个最低值：

in_list = [1, 2, 3, 4, 5, 6]
input: function(in_list, 3)
output: [1, 2, 3]

Answer 1

你可以使用heapq.nsmallest：

>>> from heapq import nsmallest
>>> in_list = [1, 2, 3, 4, 5, 6]
>>> nsmallest(3, in_list)
[1, 2, 3]
>>>

Answer 2

如果您可以排序，您可以获得前3个元素，如下所示：

 alist=[6, 4, 3, 2, 5, 1]
 sorted(alist)[:3]

输出：

 [1,2,3]

Answer 3

没有模块导入更简单：

l =[3,8,9,10,2,4,1]
l1 = sorted(l)[:3]

希望这可以帮助

Answer 4

如果您的列表很长，最有效的方法是通过numpy.partition：

>>> def lowest(a, n): return numpy.partition(a, n-1)[:n]
>>> in_list = [6, 4, 3, 2, 5, 1]
>>> lowest(in_list, 3)
array([1, 2, 3])

这在O（N）时间内执行，不像在O（NlogN）时间内操作的完整排序。节省时间来自不执行完整排序，但只需要确保n最低元素是第一个所需的最小量。因此输出不一定是排序的。

如果您需要对它们进行排序，您可以在之后进行排序（numpy.sort(lowest(in_list,3)) => array([1,2,3])）。对于大型数组，这仍然比首先对整个事物进行排序更快。

编辑：这是numpy.partition，heapq.nsmallest和sorted的速度的比较：

>>> a = numpy.random.permutation(np.arange(1000000))
>>> timeit numpy.partition(a, 2)[:3]
100 loops, best of 3: 3.32 ms per loop
>>> timeit heapq.nsmallest(3,a)
1 loops, best of 3: 220 ms per loop
>>> timeit sorted(a)[:3]
1 loops, best of 3: 1.18 s per loop

所以numpy.partition比heapq.nsmallest快66倍，对于一个拥有一百万个元素的阵列，它比sorted快355倍。这并不意味着你永远不应该使用heapq.nsmallest（这是非常灵活的），但它表明当速度很重要时避免普通列表是多么重要。

Answer 5

排序是合理的方法。如果你关心的是渐近复杂性，那么你想要在时间O（n）和空间O（1）中做到这一点。

def k_min(values, k):
    return sorted(values)[:k]

调用sorted()可以给你时间O（n * log n）和空间O（n），因此要实现O（n）时间和O（1）空间，需要不同的方法。

为此，您将遍历列表（即O（n）来自的位置）并跟踪到目前为止看到的k最小元素，这可以在恒定时间内完成（因为k在这里是一个常量）。

要跟踪最小元素，可以使用堆（模块heapq）或列表。在列表的情况下，时间是O（nk），并且在堆时间的情况下是O（nlog k）。在任何情况下，因为k对你来说是一个常数，所以整个事情总共会在n中呈线性。

使用一个列表（比堆更简单，但如果k很大，当然很糟糕），它可能看起来像这样

def k_min(values, k):
    minima = []  # len(minima) <= k + 1
    for v in values:
        minima.append(v)
        if len(minima) > k:
            minima.remove(max(minima))  # O(k) == O(1)
    return minima