解题思路 - 215 数组中的第K个最大元素

215. 数组中的第K个最大元素（原题卡片见 LeetCode Hot100 反转链表与课程表）

考点归类

分治法（Divide and Conquer）· 快速选择（QuickSelect）。要求时间复杂度为 $O(n)$，是快速排序（QuickSort）的同源兄弟算法。

与 912 快速排序的血缘关系

1. 同源发动机：二者共享同一个底层算子——单次对撞双指针分区（Partition），每次确定一个基准值在排序后的绝对正确位置。
2. 决策分歧（全治 vs 剪枝）：
   • 快排（QuickSort）：全都要！拿到分界线后，左半段与右半段两边同时递归，总规模 $n\log n$；
   • 快选（QuickSelect）：目标专一！只要第 $k$ 大（升序排好后下标 target = len - k 的数）。根据 target 与分界线的关系，每次只递归有目标的一边，另一半整段抛弃！
3. 复杂度数学降维（为什么是 $O(n)$）：
   • 每轮处理的数据量等比衰减：$n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots \approx 2n$；
   • 几何级数收敛，平均时间复杂度从 $O(n\log n)$ 戏剧性降为 $O(n)$ 线性时间！

---

算法快速记忆法（门神记忆法）

快速选择定位口诀：入左院，进右院，夹在中间直取果

两院大门看分界：循环 while (i <= j) 退出时必有 $j<i$，将数组分为左院 $[l,j]$、右院 $[i,r]$ 与中间过道。

• 比 $j$ 小，入左院：target <= j $\to$ 目标在左院，递归 qs(l, j)；
• 比 $i$ 大，进右院：target >= i $\to$ 目标在右院，递归 qs(i, r)；
• 夹中间，直取果：目标刚好卡在两院之间的过道上（全同基准区），直接返回 nums[target]！

---

两种解法实现

解法一：原地复用 912 模板（推荐，0 额外空间，心智统一）

直接复用 912 题手撕快排的原地双指针模板，完全无需死记“把基准借位到末尾再归位”的繁琐步骤：

/**
 * 215. 数组中的第K个最大元素（快速选择 原地 Hoare 双指针版）
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    const target = nums.length - k; // 升序排列后的目标索引
 
    const qs = (l, r) => {
        // 递归基：区间只剩 1 个元素，必定命中
        if (l >= r) return nums[target];
 
        // 1. 基准随机偏移 l：防有序恶心用例退化 O(n^2)
        const randomIndex = Math.floor(Math.random() * (r - l + 1)) + l;
        const pivot = nums[randomIndex];
 
        let i = l, j = r;
 
        // 2. 双指针对撞（严格小于/大于，相等停下换）
        while (i <= j) {
            while (nums[i] < pivot) i++;
            while (nums[j] > pivot) j--;
            if (i <= j) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
                j--;
            }
        }
 
        // 3. 门神法则：入左院、进右院、夹中间直取果
        if (target <= j) return qs(l, j); // 目标在左院 [l, j]
        if (target >= i) return qs(i, r); // 目标在右院 [i, r]
        return nums[target];              // 夹在中间过道，直接签收
    };
 
    return qs(0, nums.length - 1);
};

解法二：三堆法（Big / Equal / Small，超直观）

如果面试允许使用辅助数组，分三堆的写法逻辑如同日常谈话，没有任何指针边界陷阱：

var findKthLargest = function(nums, k) {
    const pivot = nums[Math.floor(Math.random() * nums.length)];
    const big = [], equal = [], small = [];
    for (const num of nums) {
        if (num > pivot) big.push(num);
        else if (num < pivot) small.push(num);
        else equal.push(num);
    }
 
    if (k <= big.length) {
        return findKthLargest(big, k);
    }
    if (k <= big.length + equal.length) {
        return pivot;
    }
    return findKthLargest(small, k - big.length - equal.length);
};

---

复杂度分析

• 时间复杂度：平均 $\Theta (n)$。在包含随机基准时，期望时间为线性 $O(n)$；最坏情况（未随机化遇单调数组）退化为 $O(n^2)$。
• 空间复杂度：
  • 解法一（原地法）：$O(\log n)$（仅递归调用栈消耗，若改写为 while 迭代则为严格 $O(1)$）；
  • 解法二（三堆法）：$O(n)$（辅助切分数组）。

---

易错点剖析

1. 第 K 大转下标：升序排序后，第 1 大在 nums.length - 1，第 $k$ 大在 nums.length - k，注意转换。
2. 基准随机化必加 + l：若忘记加偏移量，在右半区间递归时会抓到左半区间的数字，导致死循环或 TLE。
3. 门神边界方向：退出时必定 $j<i$。判定时是 target <= j 进左段，target >= i 进右段，切勿记混指针大小。

---

变体与举一反三

• 912. 排序数组：同门师兄——双边递归版本，详见 912 排序数组。
• 347. 前 K 个高频元素：哈希表计数后，用快速选择在 $O(n)$ 内切分前 K 高频。
• 最小的 k 个数（剑指 Offer 40）：快选经典变种，切出前 $k$ 小即可，不要求内部有序。

---

← 原题卡片见 LeetCode Hot100 反转链表与课程表