692.前k个高频单词

题目描述：

image.png

解：

先用Map统计词频，然后放入集合类按需排序取前k个即可。

  1. class Solution {
  2.     public List<String> topKFrequent(String[] words, int k) {
  3.         HashMap<String,Integer> map = new HashMap<String, Integer>();
  4.         for(String word : words) {
  5.             map.put(word,map.getOrDefault(word,0)+1);
  6.         }
  7.         List<String> ret = new ArrayList<String>();
  8.         for(Map.Entry<String, Integer> entry : map.entrySet()) {
  9.             ret.add(entry.getKey());
  10.         }
  11.         Collections.sort(ret,(word1,word2) -> {
  12.             return map.get(word1) == map.get(word2) ? word1.compareTo(word2) : map.get(word2) - map.get(word1);
  13.         });
  14.         return ret.subList(0,k);
  15.     }
  16. }

进阶：

小根堆优化

  1. public class Solution {
  3.      public List<String> topKFrequent(String[] words, int k) {
  4.         // 1.先用哈希表统计单词出现的频率
  5.         Map<String, Integer> count = new HashMap();
  6.         for (String word : words) {
  7.             count.put(word, count.getOrDefault(word, 0) + 1);
  8.         }
  9.         // 2.构建小根堆 这里需要自己构建比较规则 此处为 lambda 写法 Java 的优先队列默认实现就是小根堆
  10.         PriorityQueue<String> minHeap = new PriorityQueue<>((s1, s2) -> {
  11.             if (count.get(s1).equals(count.get(s2))) {
  12.                 return s2.compareTo(s1);
  13.             } else {
  14.                 return count.get(s1) - count.get(s2);
  15.             }
  16.         });
  17.         // 3.依次向堆加入元素。
  18.         for (String s : count.keySet()) {
  19.             minHeap.offer(s);
  20.             // 当堆中元素个数大于 k 个的时候，需要弹出堆顶最小的元素。
  21.             if (minHeap.size() > k) {
  22.                 minHeap.poll();
  23.             }
  24.         }
  25.         // 4.依次弹出堆中的 K 个元素，放入结果集合中。
  26.         List<String> res = new ArrayList<String>(k);
  27.         while (minHeap.size() > 0) {
  28.             res.add(minHeap.poll());
  29.         }
  30.         // 5.注意最后需要反转元素的顺序。
  31.         Collections.reverse(res);
  32.         return res;
  33.     }        
  34. }
  36. 作者：qi-ye-jun
  37. 链接：https://leetcode-cn.com/problems/top-k-frequent-words/solution/xiao-gen-dui-huo-zhe-hashbiao-pai-xu-by-9uj06/
  38. 来源：力扣（LeetCode）
  39. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。