写点什么

【LeetCode】数据流中的第 K 大元素 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 02 月 11 日

题目

设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。


请实现 KthLargest 类:


KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。

int add(int val) 将 val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。


代码

class KthLargest {    private int limit;    private PriorityQueue<Integer> queue;
public KthLargest(int k, int[] nums) { limit = k; queue = new PriorityQueue<>(k); for (int num : nums) { add(num); } } public int add(int val) { if (queue.size() < limit) { queue.add(val); } else if (val > queue.peek()) { queue.poll(); queue.add(val); }
return queue.peek(); }}
复制代码


总结

  • 这是 LeetCode 上面的一道简单题目,主要考察优先队列的使用。

  • Java 封装了 PriorityQueue,熟悉 Java 的 API 之后,就可以用来解决这个题目。

  • 这个题目使用了小根堆来解决,题目要求是返回第 k 大元素,正好适合小根堆的性质。

  • 今天是除夕,所以题目相对简单。继续坚持每日一题,祝大家新年快乐!


发布于: 2021 年 02 月 11 日阅读数: 11
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】数据流中的第 K 大元素Java题解