剑指offer【40】：topk数，小顶堆，快排实现

题目：

思路+代码：

思路：

法一：调用python sorted 方法

           时间复杂度：因为sorted也是使用饿快速排序实现饿，O(nlogn)

           空间复杂度：额外需要空间O(logn)

法二：python 小顶堆实现

           时间复杂度：n-k个数，维护小顶堆时间复杂度是O(logn), O(nlogk)

           空间复杂度：小顶堆只有k个数，O(logk)

法三：使用***，第一次确定的数看跟k比较；因为***每一次能确定基准的最终位置

           时间复杂度：O(nlogn), 最差情况，每次划分是最大值或者最小值，则需要划分n-1次，每次需要n-i次关键字比较才能确定枢轴位置，此时时间复杂度是O(n x n)

           空间复杂度：正常是log(n),但是最差情况时，需要存储n-1个值

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # 法一：调用python sorted 方法
        if not arr: return        
        return sorted(arr)[:k]

        # 法二：python 小根堆实现
        if k == 0:
            return list()
        hp = [-x for x in arr[:k]]  # 实际大的数在堆顶, hp[0]是堆顶元素
        heapq.heapify(hp)           # 把列表变成小顶堆，线性时间
        for i in range(k, len(arr)):
            if -hp[0] > arr[i]:
                heapq.heappop(hp)
                heapq.heappush(hp, -arr[i])
        res = [-x for x in hp]
        return res

    # 法三：使用***，第一次确定的数看跟k比较；因为***每一次能确定基准的最终位置

    def partition(self, nums, l, r):
        pivot = nums[r]
        i = l - 1
        for j in range(l, r):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1], nums[r] = nums[r], nums[i + 1] 
        return i + 1

    def randomized_partition(self, nums, l, r):
        i = random.randint(l, r)  # 随机确定基准
        nums[r], nums[i] = nums[i], nums[r]   # 基准和尾值交换
        return self.partition(nums, l, r)

    def randomized_selected(self, arr, l, r, k):
        pos = self.randomized_partition(arr, l, r)
        num = pos - l + 1
        if k < num:
            self.randomized_selected(arr, l, pos - 1, k)
        elif k > num:
            self.randomized_selected(arr, pos + 1, r, k - num)

    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return list()
        self.randomized_selected(arr, 0, len(arr) - 1, k)
        return arr[:k]