面试题40：最小的k个数

题目：
输入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]

提交结果：

思路一提交结果 思路二提交结果 思路三提交结果 思路四提交结果