Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Solution

class Solution:
    def quick_s(self,nums,left,right,k):
        if left==right:
            return nums[k]
        i=left
        j=right
        pivot = nums[(i+j)//2]
        
        while i<=j:
            while i<=j and nums[i]<pivot:
                i+=1
            while i<=j and nums[j]>pivot:
                j-=1
            if i <=j:
                tmp = nums[i]
                nums[i] = nums[j]
                nums[j] = tmp
                i+=1
                j-=1
        if k<=j:
            return self.quick_s(nums,left,j,k)
        elif k>=i:
            return self.quick_s(nums,i,right,k)
        else:
            return pivot
    def findKthLargest(self, nums: List[int], k: int) -> int:
        #注意找第K大的数需要len(nums)-K 
        # 第k小的是k
        return self.quick_s(nums,0,len(nums)-1,len(nums)-k)