Java 数组中的第 K 个最大元素：快速选择与堆排序

Java 数组中的第 K 个最大元素：快速选择与堆排序

一、原题回顾

题目描述：

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

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

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

示例：

示例 1:

输入：[3,2,1,5,6,4], k = 2
输出：5 

解释：排序后为 [1,2,3,4,5,6]，第 2 大的元素是 5。

示例 2:

输入：[3,2,3,1,2,4,5,5,6], k = 4
输出：4 

解释：排序后为 [1,2,2,3,3,4,5,5,6]，第 4 大的元素是 4（注意重复元素也要计算）。

提示：

• 1 ≤ k ≤ nums.length ≤ 10^5
• -10^4 ≤ nums[i] ≤ 10^4

二、原题分析

2.1 问题本质

我们需要在未排序的数组中找到第 k 大的元素，等价于找到排序后索引为 n-k 的元素（0-based）。

2.2 暴力解法及其局限性

方法 1：排序后取值

• 对数组进行排序（如 Arrays.sort()）；
• 返回 nums[n - k]。

时间复杂度：O(n log n)
空间复杂度：O(1)（原地排序）

问题：题目要求 O(n) 时间复杂度，此法不满足。

方法 2：维护大小为 k 的最小堆

• 遍历数组，维护一个大小为 k 的最小堆；
• 堆顶即为第 k 大元素。

时间复杂度：O(n log k)
空间复杂度：O(k)

问题：当 k≈n 时，退化为 O(n log n)，仍不满足 O(n) 要求。

关键洞察：我们需要一种线性时间的选择算法，而非完全排序。

三、答案构思

3.1 核心思想：分治 + 快速选择

快速选择（Quickselect） 是快速排序的变种，专用于解决'第 k 小/大元素'问题。

基本思路：

• 选择一个主元（pivot），将数组划分为两部分；
• 左部分 ≤ pivot，右部分 ≥ pivot；
• 根据 pivot 的最终位置，决定在左或右部分继续查找。

3.2 方法一：快速选择算法（推荐）

• 平均时间复杂度：O(n)
• 最坏时间复杂度：O(n²)（可通过随机化避免）
• 空间复杂度：O(log n)（递归栈）

3.3 方法二：堆排序（备选）

• 建大根堆，执行 k-1 次删除操作；
• 堆顶即为第 k 大元素。
• 时间复杂度：O(n log n)，不满足题目要求，但面试常考。

四、完整答案（Java 实现）

4.1 方法一：快速选择（双指针划分）

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 第 k 大 = 索引为 n-k 的元素（0-based）
        return quickselect(nums, 0, n - 1, n - k);
    }

    private int quickselect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        // 选择主元（这里用 left，实际可随机化）
        int pivot = nums[left];
        int i = left - 1;
        int j = right + 1;
        // 双指针划分：左边 <= pivot，右边 >= pivot
        while (i < j) {
            do i++;
            while (nums[i] < pivot);
            do j--;
            while (nums[j] > pivot);
            if (i < j) {
                swap(nums, i, j);
            }
        }
        // j 是左部分的最后一个索引
        if (k <= j) {
            return quickselect(nums, left, j, k);
        } else {
            return quickselect(nums, j + , right, k);
        }
    }

       {
           nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

4.2 方法二：堆排序（大根堆）

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        // 建大根堆
        buildMaxHeap(nums, heapSize);
        // 执行 k-1 次删除（将最大元素移到末尾）
        for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
            swap(nums, 0, i);
            heapSize--;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0]; // 堆顶即为第 k 大
    }

    // 建堆：从最后一个非叶子节点开始调整
    private void buildMaxHeap(int[] nums, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, i, heapSize);
        }
    }

    // 堆调整：维护大根堆性质
    private void maxHeapify(int[] nums, int i, int heapSize) {
        int left = 2 * i + 1;
        int right   * i + ;
           i;
         (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
         (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }
         (largest != i) {
            swap(nums, i, largest);
            maxHeapify(nums, largest, heapSize);
        }
    }

       {
           nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

快速选择更优（满足 O(n) 要求），堆排序作为备选（面试常考）。

五、代码分析

5.1 快速选择的关键点

• 划分目标：找到主元的正确位置 q；
• 递归方向：
  • 若 k <= q → 在左部分查找；
  • 否则 → 在右部分查找；
• 双指针技巧：
  • i 从左向右找 ≥ pivot 的元素；
  • j 从右向左找 ≤ pivot 的元素；
  • 交换后继续，直到 i >= j。

5.2 堆排序的关键点

• 大根堆：父节点 ≥ 子节点；
• 建堆：从 n/2 - 1 开始（最后一个非叶子节点）；
• 删除操作：
  • 交换堆顶与末尾；
  • 缩小堆大小；
  • 调整堆顶。

5.3 示例执行过程（以 [3,2,1,5,6,4], k=2 为例）

快速选择：

• 目标：找索引 6-2 = 4 的元素；
• 初始：left=0, right=5, k=4；
• 主元=3，划分后数组可能为 [2,1,3,5,6,4]，j=2；
• 因 k=4 > j=2，递归右部分 [5,6,4]；
• 最终找到 nums[4] = 5。

堆排序：

• 建堆后：[6,5,4,3,2,1]；
• 删除 1 次（k-1=1）：交换 6 和 1，调整后堆顶=5；
• 返回 5。

六、时间复杂度与空间复杂度分析

6.1 快速选择

• 平均时间复杂度：O(n)
  • 每次划分期望将问题规模减半；
  • 总操作数：n + n/2 + n/4 + ... = 2n = O(n)。
• 最坏时间复杂度：O(n²)
  • 每次划分极不平衡（如已排序数组）；
  • 解决方案：随机选择主元。
• 空间复杂度：O(log n)
  • 递归栈深度期望为 log n。

6.2 堆排序

• 时间复杂度：O(n log n)
  • 建堆：O(n)；
  • k-1 次删除：O(k log n) = O(n log n)（因 k≤n）。
• 空间复杂度：O(log n)
  • maxHeapify 递归栈。

结论：快速选择是本题的最佳解法（满足 O(n) 要求）。

七、常见问题解答（FAQ）

Q1：为什么快速选择的平均时间复杂度是 O(n)？

答：假设每次划分将数组分为 1:1，则：第 1 层：n 次比较；第 2 层：n/2 次；第 3 层：n/4 次；总计：n + n/2 + n/4 + ... = 2n = O(n)。

Q2：如何避免最坏情况 O(n²)？

答：随机选择主元。

Q3：能否用优先队列（PriorityQueue）？

答：可以，但时间复杂度为 O(n log k)，不满足题目 O(n) 要求。

Q4：为什么堆排序的时间复杂度是 O(n log n)？

答：虽然建堆是 O(n)，但我们需要执行 k-1 次删除操作，每次 O(log n)。当 k=n 时，总时间为 O(n log n)。

八、优化思路

8.1 优化 1：随机化主元（避免最坏情况）

private int quickselect(int[] nums, int left, int right, int k) {
    if (left == right) return nums[left];
    // 随机选择主元
    Random rand = new Random();
    int randomIndex = left + rand.nextInt(right - left + 1);
    swap(nums, left, randomIndex);
    int pivot = nums[left];
    // ... 其余代码不变
}

• 优点：期望时间复杂度稳定为 O(n)；
• 适用场景：对抗精心构造的测试数据。

8.2 优化 2：迭代版快速选择（避免递归栈溢出）

public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    int target = n - k;
    int left = 0, right = n - 1;
    while (left < right) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == target) {
            return nums[pivotIndex];
        } else if (pivotIndex < target) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
    return nums[left];
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[left];
    int i = left - 1, j = right + 1;
    while (i < j) {
        do i++;
        while (nums[i] < pivot);
        do j--;
        while (nums[j] > pivot);
        if (i < j) swap(nums, i, j);
    }
    return j;
}

• 优点：空间复杂度 O(1)；
• 缺点：代码稍复杂。

8.3 优化 3：三路快排（处理大量重复元素）

• 思想：将数组分为 < pivot, = pivot, > pivot 三部分；
• 优势：当有大量重复元素时，性能更好；
• 实现：略复杂，一般不需要。

九、数据结构与算法基础知识点回顾

9.1 快速选择（Quickselect）

• 来源：快速排序的变种；
• 用途：找第 k 小/大元素；
• 核心：分治 + 划分；
• 时间复杂度：平均 O(n)，最坏 O(n²)。

9.2 堆（Heap）

• 定义：完全二叉树，满足堆性质；
• 类型：
  • 大根堆：父 ≥ 子；
  • 小根堆：父 ≤ 子；
• 操作：
  • insert：O(log n)
  • extractMax/Min：O(log n)
  • buildHeap：O(n)

9.3 分治算法（Divide and Conquer）

• 步骤：
  1. 分解：将问题划分为子问题；
  2. 解决：递归解决子问题；
  3. 合并：合并子问题解。
• 本题：只解决一个子问题（非典型分治）。

9.4 随机化算法

• 目的：避免最坏情况；
• 应用：
  • 快速排序/选择；
  • 哈希表；
  • 蒙特卡洛方法。

十、面试官提问环节（模拟）

Q1：你的快速选择最坏时间复杂度是 O(n²)，如何改进？

答：通过随机选择主元，使得最坏情况的概率极低，期望时间复杂度稳定为 O(n)。

Q2：如果要求第 k 小元素，代码如何修改？

答：只需将目标索引改为 k-1（0-based）。

Q3：能否用计数排序？

答：可以！因为数据范围小（-10⁴ ~ 10⁴）：
时间复杂度：O(n + range) = O(n)，空间复杂度：O(range)。

Q4：快速选择和堆排序哪个更适合流数据？

答：堆排序更适合。因为快速选择需要全部数据，而堆可以动态维护 top-k。

Q5：为什么建堆的时间复杂度是 O(n)？

答：因为大部分节点在底层，调整代价小。数学证明：高度为 h 的节点数 ≤ n/2^(h+1)；总代价 = ∑(n / 2^(h+1)) × h = O(n)。

十一、这道算法题在实际开发中的应用

11.1 Top-K 推荐系统

• 场景：电商中'销量最高的前 k 个商品'；
• 方法：
  • 实时数据 → 用堆维护 top-k；
  • 离线数据 → 用快速选择找第 k 大。

11.2 数据库查询优化

• 场景：SELECT * FROM table ORDER BY score DESC LIMIT k；
• 优化：数据库内部使用快速选择或堆，避免全排序。

11.3 网络监控：Top-K 流量 IP

• 场景：找出流量最大的 k 个 IP 地址；
• 挑战：数据量大（TB 级）；
• 方案：
  • 离线：快速选择；
  • 在线：Count-Min Sketch + 堆。

11.4 游戏排行榜

• 场景：实时显示前 100 名玩家；
• 实现：
  • 更新分数时，用堆维护；
  • 定时全量计算时，用快速选择。

11.5 金融风控：最大交易金额

• 场景：找出单日交易金额第 k 大的客户；
• 数据：海量交易记录；
• 处理：MapReduce + 快速选择。

本质：任何需要'Top-K'或'第 K 大/小'的场景，都可用本题算法。

十二、相关题目推荐

题号	题目	关联点
[215]	数组中的第 K 个最大元素	本题
[347]	前 K 个高频元素	堆/桶排序
[451]	根据字符出现频率排序	堆
[692]	前 K 个高频单词	堆 + 自定义比较器
[703]	数据流中的第 K 大元素	堆（动态）
[973]	最接近原点的 K 个点	快速选择/堆
[1471]	数组中的 k 个最强值	快速选择

重点练习：LeetCode 703：动态数据流，必须用堆；LeetCode 973：自定义比较规则，快速选择更优。

十三、总结与延伸

13.1 核心总结

• 第 K 大元素是经典算法问题；
• 最优解：快速选择（平均 O(n)）；
• 备选解：堆排序（O(n log n)，面试常考）；
• 技巧：随机化主元、双指针划分、哨兵简化。

13.2 延伸思考

• 变种 1：找第 k 小元素？
  • 答：目标索引 = k-1。
• 变种 2：找中位数？
  • 答：k = n/2。
• 变种 3：支持动态插入？
  • 答：用堆（如 PriorityQueue）。

13.3 学习建议

1. 手写快速选择模板：形成肌肉记忆；
2. 理解划分过程：画图辅助；
3. 对比堆 vs 快速选择：知道各自适用场景；
4. 刷相关题：巩固'Top-K'模式。