215.-kth-largest-element-in-an-array.md

215. Kth Largest Element in an Array

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        return self.quick_select(nums , 0 , len(nums) - 1, k)
        
    
    def quick_select(self, nums,l , r ,k):
        
        
        ## 当这个l = r  直接选这l的值
        if l >= r : return nums[l]
        i = l - 1
        j = r + 1
        x = nums[ r + l >> 1]
        while i < j :
            i += 1
            while nums[i] > x:
                i += 1
            j -= 1
            while nums[j] < x:
                j -= 1
                
            if i < j:
                nums[i], nums[j] = nums[j], nums[i]
                
        left_length = j - l + 1
        if k <= left_length:
            return self.quick_select(nums, l, j , k)
        else:
            return self.quick_select(nums, j+ 1, r, k - left_length)