可用堆或快速选择算法求第K大元素：最小堆法时间复杂度O(n log k)、空间O(k)，适合K较小；快速选择法平均时间O(n)，基于分区思想，需随机化pivot避免最坏O(n²)。
直接用堆（优先队列）或快速选择算法，时间复杂度可降到 O(n) 平均情况，远优于先排序再取值的 O(n log n)。
用最小堆维护前 K 个最大元素
适合 K 较小（比如 Top-K 场景），空间可控，逻辑直观：
- 创建容量为 K 的最小堆（Java 中用 PriorityQueue<Integer>，并传入 Comparator.reverseOrder() 的反向是错的——要最小堆就得用默认自然顺序，或显式写 (a, b) -> Integer.compare(a, b)
- 遍历数组：若堆未满，直接 add；若已满且当前元素 > 堆顶，poll 堆顶再 add 当前元素
- 遍历结束，堆顶就是第 K 个最大元素
时间复杂度 O(n log k)，空间 O(k)。当 K = n/2 时退化为 O(n log n)，但实践中 K 通常远小于 n。
用快速选择算法（QuickSelect）
基于快排分区思想，不完全排序，只递归处理含目标位置的那一侧：
立即学习“Java免费学习笔记（深入）”；
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
- 随机选一个 pivot（强烈建议随机化，避免最坏 O(n²)）
- 用 partition 将数组划分为「≥ pivot」和「＜ pivot」两部分，返回 pivot 最终下标 pos
- 若 pos == k，直接返回 arr[pos]；若 pos > k，在左半部分递归；若 pos n−K）
平均时间 O(n)，最坏 O(n²)，空间 O(1)（迭代实现可避免递归栈）。
Java 实现关键细节提醒
别踩这些常见坑：
- 第 K 大 ≠ 索引 K：数组升序排列后，第 1 大是 arr[n−1]，第 K 大是 arr[n−K]
- PriorityQueue 默认是最小堆，不用反转；想用最大堆才需 Comparator.reverseOrder()
- Arrays.sort() 是双轴快排，对基本类型不是稳定排序，但本问题无需稳定性
- 若允许修改原数组，快选更省空间；否则复制一份再操作
简单对比与选用建议
三种主流方式实际效果：
- 排序 + 取索引：代码最短（Arrays.sort(arr); return arr[n - k];），适合数据量小或 K 不固定、后续还需其他顺序访问
- 最小堆：K 明确且偏小（如 K ≤ 100）、数据流式到达、或需多次查不同 K
- 快速选择：大数据量、单次查询、追求理论最优平均性能，面试高频考点
不复杂但容易忽略边界：k 从 1 开始计数，务必检查 1 ≤ k ≤ arr.length，否则抛 IllegalArgumentException。
