1.快排划分思路的解法

特别注意k=0的情况

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not arr or k == 0:
            return []
        self.partitionK(arr, 0, len(arr)-1, k)
        return arr[:k]

    def partitionK(self, nums, l, r, k):
        index = self.partition(nums, l, r)
        length = index - l + 1
        # print("index,nums,l,r,k, length",index,nums,l,r,k, length)
        if k > length:
            self.partitionK(nums, index+1, r, k-length)
        if k < length:
            self.partitionK(nums, l, index-1, k)

    def partition(self, nums, l, r):
        self.swap(nums, l, l+(r-l)//2)
        # print("partition,nums", nums)
        pivot = l
        index = l+1
        for i in range(index, r+1):
            # print('i,index,nums', i,index,nums)
            if nums[i] < nums[pivot]:
                self.swap(nums, index, i)
                index += 1
        # print("partition2,nums", nums)
        self.swap(nums, pivot, index-1)
        return index-1

    def swap(self, nums, i, j):
        nums[i],nums[j] = nums[j], nums[i]