题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
解法一：分治法
class Solution:def GetLeastNumbers_Solution(self, tinput, k):n = len(tinput)if k <= 0 or k > n:return list()start = 0end = n - 1mid = self.partition(tinput, start, end)while k - 1 != mid:if k - 1 > mid:start = mid + 1mid = self.partition(tinput, start, end)elif k - 1 < mid:end = mid - 1mid = self.partition(tinput, start, end)res = tinput[:mid+1]res.sort()return resdef partition(self, numbers, low, high):key = numbers[low]while low < high:while low < high and numbers[high] >= key:high -= 1numbers[low] = numbers[high]while low < high and numbers[low] <= key:low += 1numbers[high] = numbers[low]numbers[low] = keyreturn low