面试常考算法题之 Top K 问题

用户头像
码农田小齐
关注
发布于: 2020 年 09 月 16 日

大家好,这里是《齐姐聊算法》系列之 Top K 问题。



Top K 问题是面试中非常常考的算法题。





Leetcode 上这两题大同小异,这里以第一题为例。





题意:

给一组词,统计出现频率最高的 k 个。

比如说 “I love leetcode, I love coding” 中频率最高的 2 个就是 I 和 love 了。



有同学觉得这题特别简单,但其实这题只是母题,它可以升级到系统设计层面来问:



在某电商网站上,过去的一小时内卖出的最多的 k 种货物。



我们先看算法层面:



思路:



统计下所有词的频率,然后按频率排序取最高的前 k 个呗。



细节:



用 HashMap 存放单词的频率,用 minHeap/maxHeap 来取前 k 个。



实现:



  1. 建一个 HashMap <key = 单词,value = 出现频率>,遍历整个数组,相应的把这个单词的出现次数 + 1.



这一步时间复杂度是 O(n).



  1. 用 size = k 的 minHeap 来存放结果,定义好题目中规定的比较顺序

a. 首先按照出现的频率排序;

b. 频率相同时,按字母顺序。

  1. 遍历这个 map,如果

a. minHeap 里面的单词数还不到 k 个的时候就加进去;

b. 或者遇到更高频的单词就把它替换掉。



时空复杂度分析:



第一步是 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;
}
}



如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!



我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!



更多干货文章见我的 Github: https://github.com/xiaoqi6666/NYCSDE



发布于: 2020 年 09 月 16 日 阅读数: 491
用户头像

码农田小齐

关注

纽约程序媛 2020.07.06 加入

微信搜:码农田小齐

评论 (2 条评论)

发布
用户头像
TreeMap排序
2020 年 09 月 16 日 17:26
回复
TreeMap 是O(nlogn), Heap是O(nlogk)
2020 年 09 月 17 日 01:57
回复
没有更多了
面试常考算法题之 Top K 问题