题解 | #最小的K个数#

快速选择算法(quick select)
参考：https://mp.weixin.qq.com/s/TRO3FOKT90Mpvn3hQWVBAQ

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k > len(tinput) or k <0:
            return None
#         k = len(tinput)-k
        def partition(nums, lo, hi):
            if lo >= hi:
                return lo
            i,j = lo+1, hi
            p = lo
            while True:
                while(nums[i]<=nums[p]):
                    if i >= hi:
                        break
                    i += 1
                while(nums[j]>=nums[p]):
                    if j <= lo:
                        break
                    j -= 1
                if i >= j:
                    break
                nums[i], nums[j] = nums[j], nums[i]
            nums[p], nums[j] = nums[j], nums[p]
            return j
        lo, hi = 0, len(tinput)-1
        while lo <= hi:
            p = partition(tinput, lo, hi)  
            if p+1 == k:
                return tinput[0:p+1]
            elif p+1 < k:
                lo = p+1
            elif p+1 > k:
                hi  = p-1
        return None