当前位置:网站首页>PriorityQueue (large root heap / small root heap /topk problem)
PriorityQueue (large root heap / small root heap /topk problem)
2022-07-06 13:36:00 【Li bohuan】
PriorityQueue It's from JDK1.5 Start to provide new data structure interface , It's a very high priority queue based on priority heap . Priority queue is another kind of queue different from FIFO queue . Each time the element with the highest priority is removed from the queue .
By default ,PriorityQueue yes Small cap pile , As the code shows
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
queue.offer(6);
while (!queue.isEmpty()){
System.out.print(queue.poll() + " ");
}
}
Output results :
We can also construct it in the following ways Big pile top :
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);// Descending
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
queue.offer(6);
while (!queue.isEmpty()){
System.out.print(queue.poll() + " ");
}
}
Output results :
Top K problem , Power button 347 Heli button 692:
Power button 347: Give you an array of integers nums
And an integer k
, Please return to the frequency before k
High element . You can press In any order Return to the answer .
Example :
Input : nums = [1,1,1,2,2,3], k = 2 Output : [1,2]
The code is as follows : Pay attention to the construction of small top pile (o1,o2)-> o1.getValue() - o2.getValue() Don't omit .
public int[] topKFrequent(int[] nums, int k) {
//key Element value ,value For frequency of occurrence
HashMap<Integer,Integer> map = new HashMap<>();
PriorityQueue<Map.Entry<Integer, Integer>> queue
= new PriorityQueue<>((o1,o2)-> o1.getValue() - o2.getValue());
int[] res = new int[k];
for (int num : nums) {
map.put(num,map.getOrDefault(num,0) + 1);
}
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
for (Map.Entry<Integer, Integer> entry : entries) {
queue.offer(entry);
if(queue.size() > k){
queue.poll();
}
}
// What remains is the most frequent
for(int i = 0; i < k; i++){
Map.Entry<Integer, Integer> poll = queue.poll();
res[i] = poll.getKey();
}
return res;
Power button 692: Given a list of words words And an integer k , Return to the former k The most frequently used word . The answers returned should be sorted by word frequency from high to low . If different words have the same frequency , Sort in dictionary order .
Example :
Input : words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output : ["i", "love"]
analysis : "i" and "love" For the two words that appear most frequently , Are all 2 Time . Be careful , In alphabetical order "i" stay "love" Before .
This question is a little more difficult than the last one , Because when two words appear the same number of times, we should also consider sorting by dictionary , The second is that the answers need to be sorted from top to bottom , This is mainly reflected in the priority queue PriorityQueue On the structure of . The code is as follows :
public List<String> topKFrequent(String[] words, int k) {
List<String> res = new ArrayList<>();
//key For the elements ,value For frequency of occurrence
HashMap<String,Integer> map = new HashMap<>();
for (String word : words) {
map.put(word,map.getOrDefault(word,0) + 1);
}
PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(
((o1, o2) -> {
if(o1.getValue() == o2.getValue()){
return o2.getKey().compareTo(o1.getKey());
}
return o1.getValue() - o2.getValue();
})
);
Set<Map.Entry<String, Integer>> entries = map.entrySet();
for (Map.Entry<String, Integer> entry : entries) {
queue.offer(entry);
if(queue.size() > k){
queue.poll();
}
}
for(int i = 0; i < k; i++){
res.add(queue.poll().getKey());
}
Collections.reverse(res);
return res;
}
Be careful o2.getKey().compareTo(o1.getKey()) Is in reverse order of the dictionary , Why do that , Because we use a small top pile here , So every time poll What comes out is the smallest frequency element , Last need reverse once , In order to cooperate with this , So when we construct the priority queue, we use the reverse order of the dictionary .
边栏推荐
- 西安电子科技大学22学年上学期《信号与系统》试题及答案
- 【九阳神功】2018复旦大学应用统计真题+解析
- 透彻理解LRU算法——详解力扣146题及Redis中LRU缓存淘汰
- View UI plus released version 1.3.0, adding space and $imagepreview components
- E-R graph to relational model of the 2022 database of tyut Taiyuan University of Technology
- There is always one of the eight computer operations that you can't learn programming
- 2.C语言初阶练习题(2)
- The overseas sales of Xiaomi mobile phones are nearly 140million, which may explain why Xiaomi ov doesn't need Hongmeng
- View UI Plus 发布 1.3.1 版本,增强 TypeScript 使用体验
- 3.猜数字游戏
猜你喜欢
9. Pointer (upper)
凡人修仙学指针-2
Alibaba cloud microservices (III) sentinel open source flow control fuse degradation component
5. Download and use of MSDN
There is always one of the eight computer operations that you can't learn programming
View UI Plus 发布 1.2.0 版本,新增 Image、Skeleton、Typography组件
IPv6 experiment
甲、乙机之间采用方式 1 双向串行通信,具体要求如下: (1)甲机的 k1 按键可通过串行口控制乙机的 LEDI 点亮、LED2 灭,甲机的 k2 按键控制 乙机的 LED1
Cookie和Session的区别
(超详细onenet TCP协议接入)arduino+esp8266-01s接入物联网平台,上传实时采集数据/TCP透传(以及lua脚本如何获取和编写)
随机推荐
最新坦克大战2022-全程开发笔记-2
Implement queue with stack
12 excel charts and arrays
[while your roommate plays games, let's see a problem]
Voir ui plus version 1.3.1 pour améliorer l'expérience Typescript
仿牛客技术博客项目常见问题及解答(三)
【九阳神功】2018复旦大学应用统计真题+解析
Solution: warning:tensorflow:gradients do not exist for variables ['deny_1/kernel:0', 'deny_1/bias:0',
vector
3.C语言用代数余子式计算行列式
为什么要使用Redis
C语言入门指南
ArrayList的自动扩容机制实现原理
C language Getting Started Guide
7. Relationship between array, pointer and array
MPLS experiment
[面试时]——我如何讲清楚TCP实现可靠传输的机制
6. Function recursion
Questions and answers of "basic experiment" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
优先队列PriorityQueue (大根堆/小根堆/TopK问题)