[Leetcode 703]流中第K个最大元素Kth Largest Element in a Stream优先队列
2021/11/29 6:06:17
本文主要是介绍[Leetcode 703]流中第K个最大元素Kth Largest Element in a Stream优先队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
找到一串数字中的第K大元素
在原数组的基础上,每次会不断插入元素
插入的同时要返回插入后第K大的元素
https://leetcode.com/problems/kth-largest-element-in-a-stream/
Design a class to find the kth
largest element in a stream. Note that it is the kth
largest element in the sorted order, not the kth
distinct element.
Implement KthLargest
class:
KthLargest(int k, int[] nums)
Initializes the object with the integerk
and the stream of integersnums
.int add(int val)
Appends the integerval
to the stream and returns the element representing thekth
largest element in the stream.
Example 1:
Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8] Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
思路
tips区别
优先队列:根据自定义的优先级(更大/更小/甚至字母abc),按照优先级大的先出
普通队列:严格的先进先出
example:https://www.liaoxuefeng.com/wiki/1252599548343744/1265120632401152
优先队列经常用在dijsktra迪杰斯特拉算法,最小堆。这题先熟悉优先队列
q=new PriorityQueue<>(k);
经过定义后,q.peek()返回的则是第K大
找第K大的元素,即只用管大元素,小元素的顺序不用管
即每次add,
如果add的元素<第K大,那他进不进队列,对第K大都没有影响,直接忽略掉,return peek;
如果add的元素>第K大,则poll/remove排出队列中最小的,offer/add进该元素,更新队列,再return peek
代码
class KthLargest { PriorityQueue<Integer> q; int k; public KthLargest(int k, int[] nums) { this.k=k; q=new PriorityQueue<>(k);//定义返回第K大的数 for(int n:nums){ add(n); } } public int add(int val) { if(q.size()<k){ //初始化 q.offer(val); } else if(q.peek()<val){ //只有当加入的值大于第K大时,才更新队列 q.poll(); q.offer(val); } //返回第K大 return q.peek(); } }
这篇关于[Leetcode 703]流中第K个最大元素Kth Largest Element in a Stream优先队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升