一开始的思路：
将所有的单词建立大根堆（按出现的次数完成大根堆的构建(如果出现次数相同，按字典顺序排序)然后按顺序弹出k个元素
class Solution { public List<String> topKFrequent(String[] words, int k) { Map<String, Integer> map = new HashMap<>(); for (String word : words) { if (map.containsKey(word)) { int val = map.get(word); // 注意我们的map.get返回的是Integer引用类型，在这个过程发生了自动拆箱 map.put(word, val + 1); } else { map.put(word, 1); } } // 程序到了这，我们把单词以及单词出现的次数储存到了Map中 // 接下来遍历单词列表中所有的key-value映射关系，储存到PriorityQueue中（建立大根堆） CountCmp countCmp = new CountCmp(); PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>(countCmp); Set set = map.entrySet(); // 返回所有的 key-value 映射关系, 返回值的类型为Set<Map.Entry<String, Integer>> for (Map.Entry<String, Integer> entry : map.entrySet()) { priorityQueue.offer(entry); } // 弹出k个堆顶元素 List<String> ret = new ArrayList<>(); for (int i = 0; i < k; ++i) { ret.add(priorityQueue.poll().getKey()); } return ret; } } // 自定义了一个比较器对象，按出现的次数完成大根堆的构建(如果出现次数相同，按字典顺序排序) class CountCmp implements Comparator<Map.Entry<String, Integer> >{ @Override public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { if (o1.getValue().equals(o2.getValue())) { return o1.getKey().compareTo(o2.getKey()); } else{ return o2.getValue().compareTo(o1.getValue()); // 因为这里获取的是Integer引用类型，所以用compareTo来比较 } } }
改进后的思路
对于前 k 大或前 k 小这类问题，有一个通用的解法：优先队列。优先队列可以在 O(logn) 的时间内完成插入或删除元素的操作（其中 n 为优先队列的大小），并可以O(1) 地查询优先队列顶端元素。
在本题中，我们可以创建一个小根优先队列（顾名思义，就是优先队列顶端元素是最小元素的优先队列）。我们将每一个字符串插入到优先队列中，如果优先队列的大小超过了 k，那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。
class Solution { public static List<String> topKFrequent(String[] words, int k) { //1、统计单词出现的次数 key:单词 val: 次数 Map<String,Integer> map = new HashMap<>(); for (String word : words) { if(map.get(word) == null) { map.put(word,1); }else { int val = map.get(word); map.put(word,val+1); } } //2、建立大小为k的 小根堆 PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() { @Override public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { //比较频率 if(o1.getValue().compareTo(o2.getValue()) == 0) { //做一个转换 return o2.getKey().compareTo(o1.getKey()); } //return o1.getValue()-o2.getValue(); return o1.getValue().compareTo(o2.getValue()); } }); //遍历map for (Map.Entry<String,Integer> entry : map.entrySet()) { if(minHeap.size() < k) { minHeap.offer(entry); }else { //此时需要和堆顶元素去比较 Map.Entry<String,Integer> top = minHeap.peek(); Integer val = top.getValue(); // entry是当前的元素 if(val.compareTo(entry.getValue())<0) { minHeap.poll(); minHeap.offer(entry); }else if(val.compareTo(entry.getValue()) == 0) { String key = top.getKey(); if(key.compareTo(entry.getKey()) > 0) { minHeap.poll(); minHeap.offer(entry); } } } } List<String> list = new ArrayList<>(); for (int i = 0; i < k; i++) { String key = minHeap.poll().getKey(); list.add(key); } Collections.reverse(list); return list; } }
