前K大的数

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]

2. 堆排序的思路

建立一个大顶堆，然后将剩下的数按次序和堆顶元素比较，如果比堆顶元素小，则交换

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if len(arr) < k:
            return arr
        # 异常case需要考虑
        if k == 0 or len(arr) == 0:
            return []
        arr[:k] = self.build(arr[:k])
        for i in range(k, len(arr)):
            # print("arr[i]",i, arr[i])
            if arr[0] > arr[i]:
                arr[0] = arr[i]
                self.adjust(arr, 0, k)
        return arr[:k]

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

    def adjust(self, nums, i, length):
        tmp = nums[i]
        k = 2*i+1
        while k < length:
            if k+1 < length and nums[k+1] > nums[k]:
                k += 1
            if k < length and nums[k] > tmp:
                nums[i] = nums[k]
                i = k
            k = 2*k+1
        nums[i] = tmp        


    def build(self, nums):
        for i in range(len(nums)//2, -1, -1):
            self.adjust(nums, i, len(nums))
        return nums
    

3. 二叉搜索树

4. 计数排序