最小的k个数

输入整数数组arr，找出最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数，最小的4个数是1、2、3、4。示例1：输入：arr=[3,2,1],k=2输出：[1,2]或[2,1]示例2：输入：arr=[0,1,2,1],k=1Output:[0]Restriction:0<=k<=arr.length<=100000<=arr[i]<=10000解题思路是在一个随机数组中寻找最小的k个数，即本质上是一个排序问题，就是把数组从小到大排序，然后取出前k个数，用前十排序算法求解。对应的时间复杂度-空间复杂度为冒泡排序：O(n2)-O(1)选择排序：O(n2)-O(1)插入排序：O(n2)-O(1)快速排序：O(nlgn)-O(lgb)堆排序：O(nlgn)-O(1)归并排序：O(nlgn)-O(n)希尔排序：O(1.3nlgn)-O(1)基数排序：O(kn)-O(n+k)countingsortingbucketsortingtestdataupto10000,5digitsnumber,使用基数排序算法复杂度为O(5n)classSolution(object):defgetLeastNumbers(self,arr,k):""":typearr:List[int]:typek:int:rtype:List[int]"""#5digitsn=5#位数，0表示个位数i=0whileik:#左半区排序区间留到pos-1self.quick_sort(arr,left,pos-1,k)else:#左半区数组个数小于k，剩余k-需要从右半区选num个数作为整个数组数的前k个self.quick_sort(arr,pos+1,right,k-num)defrandom_select(self,arr,left,right):#随机左右选择一个位置pos=random.randint(left,right)#交换这个位置和左边位置的值arr[pos],arr[left]=arr[left],arr[pos]returnposdefpartition(self,arr,left,right):"""分区函数:typearr:List[int]:typeleft:分区的左起始位置:typeright:分区的右结束位置"""#随机选择一个值和与左位置交换self.random_select(arr,left,right)#取出分区选择的中间值，左半区域需要小于这个值，右半区域大于这个值temp_value=arr[left]whilelefttemp_value:#从右往左推进，遇到第一个比中间值小的数，就放到原来中间值的位置，也就是左边的位置right-=1arr[left]=arr[right]whileleft