这篇文章主要讲解了“怎么使用heap和map”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“怎么使用heap和map”吧！
Top K 问题是面试中非常常考的算法题。
Leetcode 上这两题大同小异，这里以第一题为例。
题意：
给一组词，统计出现频率最高的 k 个。
比如说 “I love leetcode, I love coding” 中频率最高的 2 个就是 I 和 love 了。
有同学觉得这题特别简单，但其实这题只是母题，它可以升级到<span >系统设计</span>层面来问：
在某电商网站上，过去的一小时内卖出的最多的 k 种货物。
我们先看算法层面:
<span >思路：
统计下所有词的频率，然后按频率排序取最高的前 k 个呗。
<span >细节：
用 HashMap 存放单词的频率，用 minHeap/maxHeap 来取前 k 个。
<span >实现：
建一个 HashMap <key = 单词，value = 出现频率>，遍历整个数组，相应的把这个单词的出现次数 + 1.
这一步时间复杂度是 O(n).
用 size = k 的 minHeap 来存放结果，定义好题目中规定的比较顺序
a. 首先按照出现的频率排序；
b. 频率相同时，按字母顺序。
遍历这个 map，如果
a. minHeap 里面的单词数还不到 k 个的时候就加进去；
b. 或者遇到更高频的单词就把它替换掉。
<span >时空复杂度分析：
第一步是 O(n)，第三步是 nlog(k)，所以加在一起时间复杂度是 O(nlogk).
用了一个额外的 heap 和 map，空间复杂度是 O(n).
代码：
计算
安全
数据库
网络和加速
企业服务
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// Step 1
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
Integer count = map.getOrDefault(word, 0);
count++;
map.put(word, count);
}
// Step 2
PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k+1, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
if(e1.getValue() == e2.getValue()) {
return e2.getKey().compareTo(e1.getKey());
}
return e1.getValue().compareTo(e2.getValue());
}
});
// Step 3
List<String> res = new ArrayList<>();
for(Map.Entry<String, Integer> entry : map.entrySet()) {
minHeap.offer(entry);
if(minHeap.size() > k) {
minHeap.poll();
}
}
while(!minHeap.isEmpty()) {
res.add(minHeap.poll().getKey());
}
Collections.reverse(res);
return res;
}
}感谢各位的阅读，以上就是“怎么使用heap和map”的内容了，经过本文的学习后，相信大家对怎么使用heap和map这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4612374/blog/4572201
