可用堆或快速选择算法求第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，并传入 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）

基于快排分区思想，不完全排序，只递归处理含目标位置的那一侧：

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。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南