215. Kth Largest Element in an Array

快排 双指针

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

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

Example 2:

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

Constraints:

• 1 <= k <= nums.length <= 105

• -104 <= nums[i] <= 104

分析

注意第k大就是N-K+1小，N-K就是索引。所以后面直接返回nums[k]

partition函数每次返回左范围右边界。

注意判断条件是l<=r，对比二分l+1<r

def findKthLargest(nums, k):
    n = len(nums)
    k = n - k  # 转换为第k小的索引
    low, high = 0, n - 1
    
    while low <= high:
        pivot_pos = partition(low, high)
        
        if pivot_pos < k:
            low = pivot_pos + 1
        elif pivot_pos > k:
            high = pivot_pos - 1
        else:
            return nums[k]
    return nums[k]

def partition(low, high):
    pivot = nums[(low + high) // 2]
    l, r = low, high
    while l <= r:
        while l <= r and nums[l] < pivot: l += 1
        while l <= r and nums[r] > pivot: r -= 1
        if l <= r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
    return r  # 或者 return l-1（两者等价）