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

Question

我想知道怎么从一个列表中找出3个最小的值。比如说，我想从这个列表中获取3个最小的值：

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

Answer 1

排序是一个合理的方法。不过，如果你在意算法的复杂度，那就需要在时间上做到 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 对你来说是个常量，整体的时间复杂度最终都会是线性的 O(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

Answer 2

如果你的列表很长，最有效的方法是使用 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 3

没有导入模块的话，甚至可以更简单：

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

希望这能帮到你

Answer 4

如果你能进行排序，那么你可以像下面这样获取前三个元素：

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

输出结果：

 [1,2,3]

Answer 5

你可以使用 heapq.nsmallest 这个功能：

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