题目
给一非空的单词列表，返回前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) 空间复杂度解决。
思路
遍历计数每个单词的个数，用哈希表保存，再对哈希表进行排序（分别对key和value进行排序，先对key进行排序，再对value进行排序），然后取出排序后的哈希表前k个数据。
代码
语言：Java
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> map = new HashMap<>();
if(words.length < 1) {
return null;
}
map.put(words[0], 1);
int count = 1;
boolean isNotFound = true;
for (int i = 1; i < words.length; i++) {
for (int j = 0; j < i; j++) {
isNotFound = true;
count = map.get(words[j]);
if(words[i].equals(words[j])) {
count++;
isNotFound = false;
break;
}
}
// 没找到，即没出现过，个数为1
if(isNotFound) {
count = 1;
}
map.put(words[i], count);
}
// 按键排序
map = sortMapByKey(map);
// 按值排序
map = sortMapByValue(map);
List<String> resultList = new ArrayList<>();
int temp = 1;
for(String key : map.keySet()){
if(k < temp) {
break;
}
resultList.add(key);
temp++;
}
return resultList;
}
public static Map<String, Integer> sortMapByValue(Map<String, Integer> oriMap) {
if (oriMap == null || oriMap.isEmpty()) {
return null;
}
Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
List<Map.Entry<String, Integer>> entryList = new ArrayList<Map.Entry<String, Integer>>(oriMap.entrySet());
Collections.sort(entryList, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return o2.getValue() - o1.getValue();
}
});
Iterator<Map.Entry<String, Integer>> iter = entryList.iterator();
Map.Entry<String, Integer> tmpEntry = null;
while (iter.hasNext()) {
tmpEntry = iter.next();
sortedMap.put(tmpEntry.getKey(), tmpEntry.getValue());
}
return sortedMap;
}
public static Map<String, Integer> sortMapByKey(Map<String, Integer> map) {
if (map == null || map.isEmpty()) {
return null;
}
Map<String, Integer> sortMap = new TreeMap<String, Integer>(
new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}});
sortMap.putAll(map);
return sortMap;
}
}
力扣官方代码
！！！只需进行一次哈希表排序，在值(频率)相同时，进行键值的比较
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> cnt = new HashMap<String, Integer>();
for (String word : words) {
cnt.put(word, cnt.getOrDefault(word, 0) + 1);
}
List<String> rec = new ArrayList<String>();
for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
rec.add(entry.getKey());
}
Collections.sort(rec, new Comparator<String>() {
public int compare(String word1, String word2) {
return cnt.get(word1) == cnt.get(word2) ? word1.compareTo(word2) : cnt.get(word2) - cnt.get(word1);
}
});
return rec.subList(0, k);
}
}
