题目描述： 给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
示例 1：
输入: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2 输出: [“i”, “love”] 解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 “i” 在 “love” 之前。
示例 2：
输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4 输出: [“the”, “is”, “sunny”, “day”] 解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词， 出现次数依次为 4, 3, 2 和 1 次。
注意：
假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。 输入的单词均由小写字母组成。
扩展练习：
尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。 emm使用笨方法 用map按照value进行排序，比较烂的方法
class Solution { public List<String> topKFrequent(String[] words, int k) { List<String> result = new ArrayList<>(k); if (k == words.length) { for (String string : words) { result.add(string); } Collections.sort(result); return result; } else { Map<String, Integer> map = new TreeMap<String, Integer>(); for (String string : words) { map.put(string,map.getOrDefault(string, 0) + 1); } List<Map.Entry<String, Integer>> list = map.entrySet().stream() .sorted((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue())) .collect(Collectors.toList()); int index = 0; for(Map.Entry<String,Integer> mapping:list){ if(index ++ < k){ result.add(mapping.getKey()); }else { break; } } return result; } } }看看别人使用前缀树如何实现的
/** * 使用前缀树 */ class MagicDictionary { class PreTree { public char value;//当前前缀树的节点内容---字符 public int count;//以当前前缀树节点结尾的字符串的计数 public HashMap<Character, PreTree> subTree;//当前前缀树的子节点 public PreTree(char v) { this.value = v; this.count = 0; this.subTree = new HashMap<>(); } public void buildTree(char[] strs, int index, PreTree root) { int len = strs.length; if (len == 0) { return; } if (index == len) { root.count++; return; } if (!root.subTree.containsKey(strs[index])) { PreTree node = new PreTree(strs[index]); root.subTree.put(strs[index], node); } buildTree(strs, index + 1, root.subTree.get(strs[index])); } } public PreTree root = null; /** * Initialize your data structure here. */ public MagicDictionary() { root = new PreTree(' '); } /** * Build a dictionary through a list of words */ public void buildDict(String[] dict) { int len = dict.length; for (int i = 0; i < len; i++) { root.buildTree(dict[i].toCharArray(), 0, root); } } /** * Returns if there is any word in the trie that equals to the given word after modifying exactly one character */ public boolean search(String word) { if (subSearch(root, word.toCharArray(), 0, 0) == 1) return true; else return false; } /** * @param root * @param str * @param index * @param flag 当前状态是不是已经又字符改变过了，0：没变过，1：已经有一个字符改变过了 * @return 是否找到正确解，，1：找到，0：没找到 */ public int subSearch(PreTree root, char[] str, int index, int flag) { if (str.length == 0) return 0; char currChar = str[index]; if (index == str.length - 1) { if (flag == 0) {//之前没有更换过字符 for (char i = 'a'; i <= 'z'; i++) { if (i != currChar) { if (root.subTree.containsKey(i) && root.subTree.get(i).count > 0) return 1; } else continue; } return 0; } else {//之前更换过 if (root.subTree.containsKey(currChar) && root.subTree.get(currChar).count > 0) return 1; else return 0; } } if (flag == 0) {//之前没有换过字符 //更换个当前字符试试（虽然是“更换”了当前字符，，但是并没有字符数组中改变任何值） for (char i = 'a'; i <= 'z'; i++) { if (currChar != i) { if (root.subTree.containsKey(i) && subSearch(root.subTree.get(i), str, index + 1, 1) == 1) return 1; } else continue; } //保持当前字符不变 if (root.subTree.containsKey(currChar)) { if (subSearch(root.subTree.get(currChar), str, index + 1, 0) == 1) return 1; } } else {//之前换过字符 if (!root.subTree.containsKey(currChar)) { return 0; } else { return subSearch(root.subTree.get(currChar), str, index + 1, 1); } } return 0; } } class Solution { public List<String> topKFrequent(String[] words, int k) { if (words.length == 0) return new ArrayList<>(); Map<String, Integer> freqMap = new HashMap<>(); for (String word : words) { freqMap.put(word, freqMap.getOrDefault(word, 0) + 1); } // 创建按照频率区分的桶,桶的大小为单词数量大小+1(bucket[0]肯定没有数据)，即假设所有单词的频率都一样 List<String>[] buckets = new List[words.length + 1]; // 给桶中放入数据，单词的频率即桶的下标，故桶天然已经排好顺序 for (Map.Entry<String, Integer> entry : freqMap.entrySet()) { int freq = entry.getValue(); String word = entry.getKey(); if (buckets[freq] == null) { buckets[freq] = new ArrayList<>(); } buckets[freq].add(word); } List<String> result = new ArrayList<>(); for (int i = buckets.length - 1; i >= 0 && k > 0; i--) { if (buckets[i] == null) continue; // 给单词排序 Collections.sort(buckets[i]); List<String> temp = buckets[i].subList(0, Math.min(buckets[i].size(), k)); result.addAll(temp); k -= temp.size(); } return result; } }