692. 前K个高频单词

# 题目

## 692. 前 K 个高频单词

[https://leetcode-cn.com/problems/top-k-frequent-words/](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 ≤ 集合元素数。
输入的单词均由小写字母组成。
```

# 题解

## 思路

将字符串用哈希表存起来，再进行排序。

## 代码

```javascript
/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function(words, k) {
    const map = new Map();
    // 哈希表
    words.forEach(word => {
        map.set(word, (map.get(word) || 0) + 1)
    });
    const res = [];
    for(const key of map.keys()){
        res.push(key);
    }
    // 排序
    res.sort((a, b) => {
        return map.get(a) === map.get(b) ? a.localeCompare(b) : map.get(b) - map.get(a);
    });
    return res.slice(0, k);
};
```

## 官方

### 方法一：哈希表 + 排序

**思路及算法**

我们可以预处理出每一个单词出现的频率，然后依据每个单词出现的频率降序排序，最后返回前 kkk 个字符串即可。

具体地，我们利用哈希表记录每一个字符串出现的频率，然后将哈希表中所有字符串进行排序，排序时，如果两个字符串出现频率相同，那么我们让两字符串中字典序较小的排在前面，否则我们让出现频率较高的排在前面。最后我们只需要保留序列中的前 kkk 个字符串即可。

**代码**

```javascript
var topKFrequent = function(words, k) {
    const cnt = new Map();
    for (const word of words) {
        cnt.set(word, (cnt.get(word) || 0) + 1);
    }
    const rec = [];
    for (const entry of cnt.keys()) {
        rec.push(entry);
    }
    rec.sort((word1, word2) => {
        return cnt.get(word1) === cnt.get(word2) ? word1.localeCompare(word2) : cnt.get(word2) - cnt.get(word1);
    })
    return rec.slice(0, k);
};
```

### 方法二：优先队列

**思路及算法**

对于前 kkk 大或前 kkk 小这类问题，有一个通用的解法：优先队列。优先队列可以在 O(log⁡n)O(\log n)O(logn) 的时间内完成插入或删除元素的操作（其中 nnn 为优先队列的大小），并可以 O(1)O(1)O(1) 地查询优先队列顶端元素。

在本题中，我们可以创建一个小根优先队列（顾名思义，就是优先队列顶端元素是最小元素的优先队列）。我们将每一个字符串插入到优先队列中，如果优先队列的大小超过了 kkk，那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 kkk 个元素就是前 kkk 个出现次数最多的单词。

**代码**

```java
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);
        }
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
                return entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();
            }
        });
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> ret = new ArrayList<String>();
        while (!pq.isEmpty()) {
            ret.add(pq.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}
```