堆

数组中的第 K 个最大元素

中等#215Java时间 O(n log k)空间 O(k)

题目要做什么

返回数组排序后第 k 大的元素,重复值按出现次数计入。

题目示例输入nums = [3,2,1,5,6,4], k = 2
题目示例输出5

01 为什么这样做

只保留目前最大的 k 个元素,用小根堆让保留元素的最小值位于根。加入新值后若数量超限,就删去最小值。最终堆顶是第 k 大。

始终成立的条件

处理完一个输入后,堆包含已见元素中最大的至多 k 个值。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int findKthLargest(int[] nums, int k) {3        PriorityQueue<Integer> heap = new PriorityQueue<>();4        for (int value : nums) {5            heap.add(value);6            if (heap.size() > k) heap.remove();7        }8        return heap.peek();9    }10}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索