在Python中大小为N的未排序列表中获取k个最小数字的最快方法？

在Python中大小为N的未排序列表中获取k个最小数字的最快方法？

您可以使用堆队列；在O（NlogK）时间中，它可以从大小N的列表中为您提供K个最大或最小的数字。

Python标准库包含

heapq

模块，并带有已实现的

heapq.nsmallest()

功能：

import heapqk_smallest = heapq.nsmallest(k, input_list)

在内部，这将使用输入列表的前K个元素创建大小为K的堆，然后遍历其余的NK个元素，将每个元素推入堆，然后d出最大的一个。这样的推入和d出 *** 作花费日志K时间，从而使总体 *** 作为O（NlogK）。

该功能还优化了以下边缘情况：

• 如果K为1，

  min()

  则使用该函数，结果为O（N）。
• 如果K> = N，则该函数改用排序，因为在这种情况下O（NlogN）会胜过O（NlogK）。

更好的选择是使用introselect算法，该算法提供O（n）选项。我知道的唯一实现是使用

numpy.partition()

功能：

import numpy# assuming you have a python list, you need to convert to a numpy array firstarray = numpy.array(input_list)# partition, slice back to the k smallest elements, convert back to a Python listk_smallest = numpy.partition(array, k)[:k].tolist()

除了需要安装之外

numpy

，这还占用了N个内存（相对于K而言

heapq

），因为为分区创建了列表的副本。

如果只需要索引，则可以将其用于任一变体：

heapq.nsmallest(k, range(len(input_list)), key=input_list.__getitem__)  # O(NlogK)numpy.argpartition(numpy.array(input_list), k)[:k].tolist()  # O(N)