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

概述使用 python在大小为N的未排序列表中获取k个最小数字的最快方法是什么？ 对大数字列表进行排序,然后获得k个最小数字,或者通过在列表中找到k次中的最小值来获得k个最小数字,确保在下一个搜索之前从搜索中删除找到的最小数字？ 您可以使用堆队列;它可以在O(NlogK)时间内从大小为N的列表中提供K个最大或最小的数字. Python标准库包括heapq module,完成了heapq.nsmalle 使用 python在大小为N的未排序列表中获取k个最小数字的最快方法是什么？
对大数字列表进行排序,然后获得k个最小数字,或者通过在列表中找到k次中的最小值来获得k个最小数字,确保在下一个搜索之前从搜索中删除找到的最小数字？解决方法 您可以使用堆队列;它可以在O(NlogK)时间内从大小为N的列表中提供K个最大或最小的数字.

Python标准库包括heapq module,完成了heapq.nsmallest() function就绪实现：

import heapqk_smallest = heapq.nsmallest(k,input_List)

在内部,这会创建一个大小为K的堆,其中包含输入列表的前K个元素,然后迭代剩余的N-K个元素,将每个元素推送到堆中,然后d出最大的元素.这样的推送和d出需要记录K时间,使得整个 *** 作O(NlogK).

该函数还优化了以下边缘情况：

>如果K为1,则使用min()函数,给出O(N)结果.
>如果K> = N,则函数使用排序,因为在这种情况下O(NlogN)将击败O(NlogK).

更好的选择是使用introselect algorithm,它提供O(n)选项.我所知道的唯一实现是使用numpy.partition() function：

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个内存(与heapq相比为K),因为为分区创建了列表的副本.

如果您只想要索引,则可以使用以下任一变量：

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

总结

以上是内存溢出为你收集整理的在python中获取大小为N的未排序列表中获取k个最小数字的最快方法？全部内容，希望文章能够帮你解决在python中获取大小为N的未排序列表中获取k个最小数字的最快方法？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。