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

题目链接：215. 数组中的第K个最大元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

核心思考：快速选择（Quickselect）算法

要在 $O(n)$ 的期望时间内求出第 $k$ 大元素，常规的排序（$O(n \log n)$）是不符合要求的。最优解法是采用快速选择（Quickselect），它是快速排序的一种变体。

1. 基本思想：
   • 快速排序的 partition（切分）操作会将数组分成两部分：一部分小于基准值（pivot），一部分大于基准值。
   • partition 返回的下标 i 意味着当前基准值排好序后在数组中的绝对位置。
   • 寻找“第 $k$ 大个元素”，即寻找排序后下标为 n - k 的元素（假设升序）。
2. 分治策略：
   • 如果 i == target_index，我们直接找到了目标值。
   • 如果 i > target_index，说明目标值在左半部分，我们只需对左侧继续递归搜索。
   • 如果 i < target_index，说明目标值在右半部分，我们只需对右侧继续递归搜索。
3. 随机化优化：
   • 为了防止在极端不平衡的数据（如已排序数组）下退化为 $O(n^2)$，代码采用了 randint 随机选择基准值，保证期望时间复杂度为 $O(n)$。

解题思路 (Python)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 寻找第k大，等价于寻找升序后下标为 n-k 的数
        target_index = n - k
        left, right = 0, n - 1
        
        while True:
            # 执行切分操作，确定一个元素的固定位置 i
            i = self.partition(nums, left, right)
            if i == target_index:
                return nums[i]
            if i > target_index:
                # 目标在左侧
                right = i - 1
            else:
                # 目标在右侧
                left = i + 1

    def partition(self, nums, left, right):
        # 随机化选取 pivot 避免极端情况性能降级
        idx = randint(left, right)
        pivot = nums[idx]
        # 将 pivot 暂存到左端
        nums[idx], nums[left] = nums[left], nums[idx]

        i, j = left + 1, right 
        while True:
            # 双指针扫描
            while i <= j and nums[i] < pivot:
                i += 1
            while i <= j and nums[j] > pivot:
                j -= 1
            if i >= j:
                break
            # 交换不符合单调性的元素
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        
        # 将 pivot 换回其最终在该区间内的绝对位置
        nums[left], nums[j] = nums[j], nums[left]
        return j

复杂度分析

• 时间复杂度：期望 $O(N)$。由于我们每次只需处理一边（而不是快排的两边都处理），其递推关系为 $T(n) = T(n/2) + O(n)$，根据主定理，结果为线性。
• 空间复杂度：$O(1)$。我们直接在原数组上进行交换和指针索引。