【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

原文链接:【http://xie.infoq.cn/article/88248cdbd1614028c0cca9020】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

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

题目

代码

总结

HQ数字卡

评论