本次刷题日记的第 59 篇，力扣题为：692. 前K个高频单词，中等
一、题目描述：
找朋友，我们来找前 K 个高频单词，这个题可以应用在某篇文章中，查找出现频次最高的前 K 个单词
二、这道题考察了什么思想？你的思路是什么？
就这道题来看，我们看看都说了啥：
- 题目中给出了一个数组，顺序是乱的，数字里面的的元素是字符串，字符串分别是单词，这个单词可能是 1 个字符，也有可能是多个字符，字符个数不定
- 题目要求我们找到数组中出现频次最高的，次高，次次高直到次 k 高的单词，并将结果返回出来
分析
从题目中给出的已知信息，我们知道咱们大方向上面需要做两件事情
- 第一需要找到每个单词出现的次数，并记录下来
- 第二咱们需要将这个记录的单词数据，通过从高频词到低频次的顺序排列起来
那么问题就来了，如何完成第一件事情呢，可以选用什么样的数据结构来存单词 和其对应的次数呢，咱们可以很容易想到的是 使用 map 来处理，键值对的方式来处理，键是不会重复的，值可以累计
那么我们可以采用 哈希表的方式来处理
例如图中的例子：
| i | 2 |
| love | 2 |
| leetcode | 1 |
| coding | 1 |
那么我们如何完成第二件事情呢？
第二件事情那就是排序了，对于排序算法我们多多少少也会几种吧，当然我们可以自己实现各种排序算法，例如冒泡，插入，选择，快速排序，归并排序，桶排序等等
不过我们也可以使用 golang 自带的库来进行处理排序，例如 c/c++ 也是会有相应的算法库来处理排序的事情
那么，接下来就是一个动手撸代码的过程的
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
撸代码的时候，我们千万注意 3 点
- 哈希表要处理完善，这个是前提
- 调用 golang 库还是排序的时候，注意顺序是从大到小，别弄反了
- 最后返回排序后的数组的前 k 个元素
编码如下：
func topKFrequent(words []string, k int) []string { // 先计算频次 help := make(map[string]int,0) for _,w := range words { help[w]++ } res := make([]string, 0, len(help)) for w := range help { res = append(res, w) } sort.Slice(res,func(i,j int) bool { return help[res[i]] > help[res[j]] || help[res[i]] == help[res[j]] && res[i] < res[j] }) return res[:k] }
四、总结：
对于这种实现方式时间复杂度和空间复杂度分别是多少呢？
我们可以来仔细看看咱们的实现方式：
可以看到在我们计算每个单词频次的时候，使用的是 hash 表，理论上时间复杂度是 O(n) ， 使用 golang 库函数的排序时间复杂度是 O(mlogm) ，那么加起来就是 O(n)+O(mlogm)
对于空间复杂度呢？
我们可以看到我们引入了一个 help 作为哈希表的辅助，主要是存储字符串的种类的，如果是 m 种，那么空间复杂度是 O(m)
原题地址：692. 前K个高频单词
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
