Top K 问题是面试中非常常考的算法题。
Leetcode 上这两题大同小异，这里以第一题为例。
题意：给一组词，统计出现频率最高的 k 个。比如说 “I love leetcode, I love coding” 中频率最高的 2 个就是 I 和 love 了。
有同学觉得这题特别简单，但其实这题只是母题，它可以升级到<span style="color:blue;font-weight:bold;">系统设计</span>层面来问：
在某电商网站上，过去的一小时内卖出的最多的 k 种货物。
我们先看算法层面:
<span style="color:orangered;font-weight:bold;">思路：
统计下所有词的频率，然后按频率排序取最高的前 k 个呗。
<span style="color:orangered;font-weight:bold;">细节：
用 HashMap 存放单词的频率，用 minHeap/maxHeap 来取前 k 个。
<span style="color:orangered;font-weight:bold;">实现：
- 建一个
HashMap <key = 单词，value = 出现频率>，遍历整个数组，相应的把这个单词的出现次数 + 1.这一步时间复杂度是 O(n).
- 用 size = k 的 minHeap 来存放结果，定义好题目中规定的比较顺序
a. 首先按照出现的频率排序；
b. 频率相同时，按字母顺序。
- 遍历这个 map，如果
a. minHeap 里面的单词数还不到 k 个的时候就加进去；
b. 或者遇到更高频的单词就把它替换掉。
<span style="color:orangered;font-weight:bold;">时空复杂度分析：
第一步是 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 点，云自习室里不见不散！
