题解 | #最小的K个数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        if k==0:
            return []
        if not input or k>=len(input):
            return input
        self.partition(input,0,len(input)-1,k-1)
        return input[:k]
    
    def partition(self,input,left,right,k):
        x = input[right]
        i = left-1
        for j in range(left,right):
            if input[j]<x:
                i+=1
                input[i],input[j] = input[j],input[i]
        i += 1
        input[i],input[right] = input[right],input[i]
        if i == k:
            return
        if i<k:
            self.partition(input, i+1, right, k)
        else:
            self.partition(input, left, i-1, k)