【LeetCode】数组中第K大的元素

1.题目

2. 思想

手写快排，然后得到第k个最大元素

3. 代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        self.quickSort(nums,0,len(nums)-1) # 排序 
        # print(nums)
        return nums[-k]
    
    def quickSort(self,nums,left,right):
        if left >= right: # 递归边界
            return
        mid = self.partition(nums,left,right)
        self.quickSort(nums,left,mid-1) # 左半部分快排
        self.quickSort(nums,mid+1,right) # 右半部分快排
    
    # 将区间分成左右两部分(对每个部分进行快排)
    def partition(self,nums,left,right):
        pivot = nums[left]
        pre_left = left
        while(left < right):            
            while(left < right and nums[right] >= pivot):                
                right -= 1
            nums[left] = nums[right]

            while(left < right and nums[left] <= pivot):
                left += 1
            nums[right] = nums[left]            
        
        nums[left] = pivot
        # 返回pivot的坐标 
        # print(nums)
        return right

最后为了避免被特殊数据坑，我们可以在取pivot值的时候，稍微做一个变换。

mid = (left+right)//2
# 交换两个未知的值
nums[mid],nums[left] = nums[left],nums[mid]
pivot = nums[left]