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

import random

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

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