mq046.数组中的第K大个最大元素

import random
import heapq

class Solution:
    def findKthLargest1(self, nums: List[int], k: int) -> int:
        t = len(nums) - k
        l, r = 0, len(nums)-1
        while True:
            index = self.quickSort(nums, l, r)
            if index == t:
                return nums[index]
            elif index > t:
                r = index - 1
            else:
                l = index + 1

    def quickSort(self, nums, left, right):
        random_index = random.randint(left, right)
        nums[left], nums[random_index] = nums[random_index], nums[left]
        # if left >= right:
        #     return
        i, j = left, right
        pivot = nums[i]
        while i < j:
            while i < j and nums[j] >= pivot:
                j -= 1
            nums[i] = nums[j]
            while i < j and nums[i] <= pivot:
                i += 1
            nums[j] = nums[i]
        nums[i] = pivot
        return i

    def findKthLargest2(self, nums: List[int], k: int) -> int:
        size = len(nums)
        heap = []
        for i in range(k):
            heapq.heappush(heap, nums[i])
        for i in range(k, size):
            top = heap[0]
            if nums[i] > top:
                heapq.heapreplace(heap, nums[i])
        return heap[0]