题目
给定一个长度为 n 的可能有反复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意程序皆可)。
要求：空间复杂度 O(n)O(n) ，工夫复杂度 O(nlogn)O(nlogn)
输出：[4,5,1,6,2,7,3,8],4 返回值：[1,2,3,4]阐明：返回最小的4个数即可，返回[1,3,2,4]也能够 输出：[1],0返回值：[]输出：[0,1,2,1,2],3返回值：[0,1,1]思路
第一工夫想到的做法是，利用排序算法，将整个数组从小到大排序，而后选取前k个数，就是该数组的最小的k个数了。
然而，这个做法不是最优的。题目只要求返回最小的k个数，并不要求这k个数也要按程序排好。所以要好好利用这个条件。
更高效的思路是，利用疾速排序的思维，通过基准值，将数组分成小于基准值局部、大于等于基准值局部。只是大体上划分出了较小的局部、和较大的局部，并没有对每个数值都进行排序，这也正好合乎题目的条件。
所以，咱们利用疾速排序的思路：
- 如果小于基准值局部的元素刚好是k个，那么就间接得出了后果
- 如果小于基准值局部的元素多余k个，那么就在小于局部再去执行快排，直到较小局部刚好是k个
- 如果小于基准值局部的元素少于k个，那么就在大于局部去执行快排，直到新的较小局部加上之前的较小局部刚好是k个
def GetLeastNumbers_Solution(input, k): def quickSort(nums,left,right,index): # 数组进入快排操作，返回快排后的基准值索引 mid = partition(nums,left,right) # 如果基准值索引 刚好等于 k，阐明基准值后面的数，刚好是最小的k个数 if mid==index: return nums[:index] # 如果基准值索引 > k，阐明以后较小局部的个数多于k个，较小局部持续快排 # 直到mid==index，刚好找到k个最小的数，将后果一层层向上返回 elif mid > index: return quickSort(nums,left,mid-1,index) # 如果基准值索引 < k，阐明以后较小局部的个数少于k个，还有局部最小k个数在较大局部中 # 较大局部进入快排，当mid==index时，mid后面就是最小的k个数，将后果一层层向上返回 else: return quickSort(nums,mid+1,right,index) # 快排操作 def partition(nums,left,right): # 基准值 pivot = nums[left] while left<right: while left<right and nums[right]>=pivot: right-=1 nums[left]=nums[right] while left<right and nums[left] <= pivot: left+=1 nums[right]=nums[left] nums[left]=pivot return left n = len(input) # 边界状况 if k<=0: return [] if k == n: return input # 快排递归 return quickSort(input,0,n-1,k)