劍指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]