692. 前K个高频单词

[力扣原题链接](https://leetcode-cn.com/problems/top-k-frequent-words/)

## 题目

给一非空的单词列表，返回前`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 ≤ 集合元素数。```
* ```输入的单词均由小写字母组成。```

**扩展练习：**

1. 尝试以 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);
    }
}
```