数组中的第K个最大元素

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

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

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

思路分析

问题理解

找第 K 大元素，最直观的方法是排序后取第 K 个，但时间复杂度是 O(nlogn)。题目要求 O(n)，需要更高效的算法。

常见解法对比

方法	时间复杂度	空间复杂度	说明
排序	O(nlogn)	O(logn)	不满足题目要求
堆（大小为 K）	O(nlogK)	O(K)	接近但不是 O(n)
快速选择	O(n) 平均	O(logn)	✅ 最优解

快速选择算法（Quick Select）

核心思想：基于快速排序的 partition 思想，但只递归处理包含目标的那一半。

回顾快速排序：

• 选一个基准值 pivot，将数组分成两部分
• 左边都 ≥ pivot，右边都 ≤ pivot（降序排列找第 K 大）
• 递归处理两边

快速选择的优化：

• partition 后，判断第 K 大在左半边还是右半边
• 只递归其中一边，另一边直接丢弃
• 这就是为什么平均时间复杂度是 O(n)：n + n/2 + n/4 + ... ≈ 2n

算法流程

1. 选择基准值：取中间位置 x = nums[(l + r) / 2]
2. Partition：用双指针将数组分成两部分
   • 左边 [l, j]：所有元素 ≥ x
   • 右边 [j+1, r]：所有元素 ≤ x
3. 判断 K 的位置：
   • 如果 k <= leftLength，第 K 大在左边，递归左边
   • 否则，第 K 大在右边，递归右边（注意 k 要减去左边的长度）
4. 递归终止：当 l == r 时，找到答案

为什么用降序？

题目求第 K 大，所以让大的数在左边更直观：

• 左边放大于等于 pivot 的数
• 这样左边第 1 个就是最大的，第 K 个就是第 K 大

复杂度分析

• 时间复杂度：O(n) 平均，O(n²) 最坏（可通过随机选 pivot 优化）
• 空间复杂度：O(logn)，递归栈深度

代码实现

/**
 * 题目：215. 数组中的第K个最大元素
 * 链接：<a href="https://leetcode.cn/problems/kth-largest-element-in-an-array/">...</a>
 */
public class P215findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, 0, nums.length - 1, k);
    }

    private int quickSort(int[] nums, int l, int r, int k) {
        if (l == r) {
            return nums[l];
        }
        int i = l - 1, j = r + 1;
        int x = nums[l + r >> 1];
        while (i < j) {
            do {
                i++;
            } while (nums[i] > x);
            do {
                j--;
            } while (nums[j] < x);
            if (i < j) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        // [l, j] [j + 1, r]
        int leftLength = j - l + 1;
        if (k <= leftLength) {
            return quickSort(nums, l, j, k);
        } else {
            return quickSort(nums, j + 1, r, k - leftLength);
        }
    }
}