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

根据快排的分割点，确定k个元素在前面还是后面加快遍历

def partition(arr, low, high):pivot_idx = random.randint(low, high)                   # 随机选择pivotarr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]     # pivot放置到最左边pivot = arr[low]                                        # 选取最左边为pivotleft, right = low, high     # 双指针while left < right:        while left<right and arr[right] >= pivot:          # 找到右边第一个<pivot的元素right -= 1arr[left] = arr[right]                             # 并将其移动到left处while left<right and arr[left] <= pivot:           # 找到左边第一个>pivot的元素left += 1arr[right] = arr[left]                             # 并将其移动到rightarr[left] = pivot           # pivot放置到中间left=right处return leftdef topKSplit(arr, low, high, k):mid = partition(arr, low, high)               # 以mid为分割点【随机选择pivot】if mid == k-1:                                      # 第k小元素的下标为k-1return arr[mid]                                 #【找到即返回】elif mid < k-1:return topKSplit(arr, mid+1, high, k)           # 递归对mid右侧元素进行排序else:return topKSplit(arr, low, mid-1, k)            # 递归对mid左侧元素进行排序n = len(nums)return topKSplit(nums, 0, n-1, n-k+1)                   # 第k大元素即为第n-k+1小元