题目：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路一：
利用python的列表操作 sort()，对其数字排序，然后取出前k个元素，复杂度O(nlogn)。
代码实现一：
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if not tinput or len(tinput)<=0 or k > len(tinput):
return []
tinput.sort()
return tinput[:k]
思路二:
利用堆进行解决，python中有heapq包，可以取出最小的k个元素，复杂度为O(n*logk)
代码实现二：
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if not tinput or len(tinput)<=0 or k > len(tinput):
return []
import heapq
return heapq.nsmallest(k,tinput)
思路三：
自己实现快速排序的思路，以便于巩固，递归实现。（需要额外空间）
代码实现三：
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if not tinput or len(tinput)<=0 or k > len(tinput):
return []
def quickSort(tinput):
if not tinput: #递归结束条件
return []
if len(tinput) == 1:
return tinput
pirvot = tinput[0]
left = quickSort([x for x in tinput[1:] if x <= pirvot])
right = quickSort([x for x in tinput[1:] if x> pirvot])
return left + [pirvot] + right
return quickSort(tinput)[:k]
思路四：
自己实现快速排序，不需要额外空间的方法
代码实现4：
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if not tinput or len(tinput)<=0 or k > len(tinput):
return []
#不分配临时数组的快速排序方法
def quicksort2(nums, left, right):
if left < right: #结束条件
q = partion(nums, left, right)
quicksort2(nums, left, q-1)
quicksort2(nums, q+1, right)
def partion(nums, left, right):
pivot = nums[right]
i = left-1
for j in range(left,right):
if nums[j] < pivot:
i+=1
nums[i],nums[j] = nums[j],nums[i] #将小于pivot的值移动到左边小于序列的下一个
nums[i+1],nums[right] = nums[right],nums[i+1] #主元位置归位
return i+1
quicksort2(tinput,0,len(tinput)-1)
return tinput[:k]
提交结果：
思路一提交结果
思路二提交结果
思路三提交结果
思路四提交结果
