题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路
思路一最好想到，就是排序，排序完成后取前K个。
思路二如下，首先根据快排的思想构建partition方法，可以选取一个基准元素，然后把数组中小于基准元素的值放在基准的左边，大的值放在右边。有了这个方法就可以连续使用这个方法，知道partition方法返回的基准的index与K相等，那就意味着在基准的左边全是比基准小的，共有K个。
第三个思路是针对处理海量数据的方法，复杂度为O(nlogk）。先构建一个大小为k的容器来存储最小的k个数字。然后设定一个范围n，每次从n中输出一个最小的数字，然后与容器中的最大值比较。
代码
def partition(arr, left, right):
pivot = arr[left]
p_index = left
for i in range(left+1,right+1):
if arr[i] < pivot:
p_index+=1
if p_index != i :
temp = arr[p_index]
arr[p_index] = arr[i]
arr[i] = temp
temp = arr[p_index]
arr[p_index] = arr[left]
arr[left] = temp
return p_index
这里的思路是选取数组的其实位置作为基准，目标是将比基准小的都放进基准的左边，比基准大的都放右边。 具体的实现，设立一个P指针，是从1开始，遍历数组，当遇到比基准小的数的时候，将这个值与P指针所指的值交换，同时P指针加一。当遇到比基准大的值的时候不用管，直接前进。这样一个遍历扫完，比基准小的值会填满位置1，2，3，4，5...，这时，P指针指向的是最后一个比基准小的值。把基准与这个值交换。就完成了交换
有了这个方法以后，剩下的代码见下面，因为答案要求是按排序顺序输出，所以结果做了排序。
def GetLeastNumbers_Solution(self, tinput, k):
if tinput is None or k > len(tinput) or k<=0 or len(tinput)<=0:
return []
l = len(tinput)-1
p_index = self.partition(tinput, 0, l)
left = 0
right = l
while p_index !=k-1:
if p_index < k-1:
left = p_index+1
p_index = self.partition(tinput, left, right)
if p_index > k-1:
right = p_index-1
p_index = self.partition(tinput, left, right)
result = tinput[:k]
result.sort()
return result
