692_前K个高频单词
package 队列.优先级队列; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.PriorityQueue; /** * https://leetcode-cn.com/problems/top-k-frequent-words/ * @author Huangyujun * map.entrySet 是结点 ,map.keySet 直接是集合 细节:优先队列的比较器的类型跟优先队列是同类型的 */ public class _692_前K个高频单词 { /** * 还是使用map存储单词 和 出现次数【细节:出现次数相等了???(涉及到细节处理)】 * 方式一:然后entrySet 获取到每个结点集合,然后可以直接使用工具类Collections 直接进行排序 * 方式二:然后通过优先队列进行排序【通过先存储k个小数据于小根堆数据,然后遍历替换掉】 * @param words * @param k * @return */ public List<String> topKFrequent(String[] words, int k) { HashMap<String, Integer> map = new HashMap<>(); int len = words.length; for(int i = 0; i < len; i++) { int frequency = map.getOrDefault(words[i], 0) + 1; map.put(words[i], frequency); } /** * map.entrySet 是结点 ,map.keySet 直接是集合 */ List list = new ArrayList<String>(map.keySet()); // Collections.sort(list, new Comparator<String>() { // @Override // public int compare(String o1, String o2) { // // return o1.compareTo(o2); // } // }); //优化在Collections 排序时加个判断条件即可 // Collections.sort(list, (a, b) -> map.get(b) - map.get(a)); //大根堆 Collections.sort(list, new Comparator<String>() { @Override public int compare(String o1, String o2) { return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1); } }); //只需要返回k个 List<String> res = new ArrayList<>(); for(int i = 0; i < k; i++) { String str = (String) list.get(i); res.add(str); } return res; } // PriorityQueue<> pQueue = new PriorityQueue<>();//没法使用优先队列,要同时存储两个数据【改成存一个】~~没法存一个,需要存两个才能满足题意【一个是数据,一个是数据的排位】 //可以使用呀,泛型参数采用结点的方式呀【这样就同时拥有两个关键不同数据】 /** * map.entrySet 是结点 ,map.keySet 直接是集合 */ public List<String> topKFrequent2(String[] words, int k) { HashMap<String, Integer> map = new HashMap<>(); int len = words.length; for(int i = 0; i < len; i++) { int frequency = map.getOrDefault(words[i], 0) + 1; map.put(words[i], frequency); } //小根堆 PriorityQueue<Map.Entry<String, Integer>> pQueueu = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() { @Override public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { return o1.getValue() == o2.getValue() ? o2.getKey().compareTo(o1.getKey()) : o1.getValue() - o2.getValue(); } } ); for(Map.Entry<String, Integer> entry : map.entrySet()) { //逻辑1: // if(pQueueu.size() == k) { // pQueueu.add(entry); // }else if(pQueueu.peek().getValue() < entry.getValue()){ // pQueueu.remove(); // pQueueu.add(entry); // } //逻辑2:【容量达到 k【细节:不是==k,而是>k】 时,都是先放入,当前值比较大,】 pQueueu.add(entry); if(pQueueu.size() > k) { pQueueu.poll(); } //我认为 逻辑1 和 逻辑2 是一样的,就是搞不懂力扣同样的逻辑,之前的题目都通过了,此题就卡壳了【我认为是力扣的原因】 } //全部遍历完毕 小根堆就结果【考虑将它转化成list 集合】 List<String> res = new ArrayList<>(); while (!pQueueu.isEmpty()) { res.add(pQueueu.poll().getKey()); } //逆序一下 Collections.reverse(res); return res; } }