好资源导航 » 文章资讯 » Python实现查找最小的k个数示例【两种解法】

Python实现查找最小的k个数示例【两种解法】

2023-09-01 19:22:04 44

本文实例讲述了Python实现查找最小的k个数。分享给大家供大家参考，具体如下：

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

解法1

使用partition函数可以知道，使用==O(N)==的时间复杂度就可以找出第K大的数字，并且左边的数字比这个数小，右边的数字比这个数字大。因此可以取k为4，然后输出前k个数字，如果需要排序的话再对结果进行排序

#-*-coding:utf-8-*-
classSolution:
defPartitionOfK(self,numbers,start,end,k):
ifk<0ornumbers==[]orstart<0orend>=len(numbers)ork>end:
return
low,high=start,end
key=numbers[low]
whilelow=key:
high-=1
numbers[low]=numbers[high]
whilelowk:
self.PartitionOfK(numbers,start,end-1,k)
defGetLeastNumbers_Solution(self,tinput,k):
#writecodehere
ifk<=0ortinput==[]ork>len(tinput):
return[]
self.PartitionOfK(tinput,0,len(tinput)-1,k)
returnsorted(tinput[0:k])
#测试：
sol=Solution()
listNum=[4,5,1,6,2,7,3,8]
rel=sol.GetLeastNumbers_Solution(listNum,4)
print(rel)

运行时间：30ms

占用内存：5732k

解法2

解法1存在两个问题，一个是partition把数组的顺序改变了，第二是无法处理海量的数据，海量的数组全部导入到内存里面做partition显然是不合适的。因此可以找出结果中最大的数字，如果遍历的数字比这个数字小，则替换，否则不变，可以采用堆的形式来实现数据结构，达到O(logK)的复杂度，因此整体的时间复杂度为N*O(logK)

#-*-coding:utf-8-*-
classSolution:
defGetLeastNumbers_Solution(self,tinput,k):
#writecodehere
iftinput==[]ork<=0ork>len(tinput):
return[]
result=[]
fornumintinput:
iflen(result)
运行结果同上
运行时间：25ms
占用内存：5724k
时间和空间占用都比解法1更优。
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。

返回顶部
514930285
czq8825@qq.com

Python实现查找最小的k个数示例【两种解法】

热门推荐

随机推荐