[692] 前K个高频单词

## [692] 前 K 个高频单词

[力扣原题地址](https://leetcode-cn.com/problems/top-k-frequent-words/)
给一非空的单词列表，返回前 *k * 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

**示例 1：**

<pre> 输入: [&#34;i&#34;, &#34;love&#34;, &#34;leetcode&#34;, &#34;i&#34;, &#34;love&#34;, &#34;coding&#34;], k = 2
 输出: [&#34;i&#34;, &#34;love&#34;]
 解析: &#34;i&#34; 和 &#34;love&#34; 为出现次数最多的两个单词，均为 2 次。
 注意，按字母顺序 &#34;i&#34; 在 &#34;love&#34; 之前。
</pre>

**示例 2：**

<pre> 输入: [&#34;the&#34;, &#34;day&#34;, &#34;is&#34;, &#34;sunny&#34;, &#34;the&#34;, &#34;the&#34;, &#34;the&#34;, &#34;sunny&#34;, &#34;is&#34;, &#34;is&#34;], k = 4
 输出: [&#34;the&#34;, &#34;is&#34;, &#34;sunny&#34;, &#34;day&#34;]
 解析: &#34;the&#34;, &#34;is&#34;, &#34;sunny&#34; 和 &#34;day&#34; 是出现次数最多的四个单词，
 出现次数依次为 4, 3, 2 和 1 次。
</pre>

**注意：**

1. 假定 *k* 总为有效值， 1 ≤ *k* ≤ 集合元素数。
2. 输入的单词均由小写字母组成。

**扩展练习：**

1. 尝试以 *O* (*n* log *k* ) 时间复杂度和 *O* (*n* ) 空间复杂度解决。

### 题解

先遍历数组数据，用 map 表保存数据。映射关系为：字符串，出现的次数。再使用一个数据，依次遍历 map 数据，将数据按照出现次数有序插入数组。时间复杂度为 O(KN).

### 代码

```cpp
class Solution {
public:
 vector<string> topKFrequent(vector<string>& words, int k) {
 std::map<string,int> tmp; //哈希表，保存字符串与出现次数的映射关系
 for(int i = 0; i < (int)words.size(); ++i)
 {
 if(tmp.count(words[i]) <= 0)
 {
 tmp[words[i]] = 0;
 }

tmp[words[i]] ++;
        }
        tmp[""] = INT_MIN;

std::vector<string> top_list;
 top_list.resize(k,""); //构造一个 k 长度的数组 依次插入数据
 for(auto it = tmp.begin();it != tmp.end(); ++it)
 {
 string tmp_str = it->first;
 bool is_first_change = true; //用于标识是插入数据还是因为插入数据导致的后续数据移位。
 for(int i = 0; i < k; ++i)
 {
 if(tmp[tmp_str] > tmp[top_list[i]] || (tmp[tmp_str] == tmp[top_list[i]] && !is_first_change))
 {
 string tmp_tmp = top_list[i];
 top_list[i] = tmp_str;
 tmp_str = tmp_tmp;
 is_first_change = false;
 }
 }
 }

return top_list;
    }
};
```