前端刷题路-Day48：前K个高频单词（题号682）

这是我参与更文挑战的第12天，活动详情查看： 更文挑战

前K个高频单词（题号682）

题目

给一非空的单词列表，返回前 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) 空间复杂度解决。

链接

leetcode-cn.com/problems/to…

解释

这题啊，这题比想象中简单。

本来还以为中等题有点简单，结果并没有，感觉可以和简单题归为一类。

首先一看题目，就已经想好解法了，只要先获取到每个单词出现的次数，之后对其进行排序即可，没有什么难度。

但真的只是这样么？

看完答案后发现原来这类取前k个或者后k个的元素都可以使用优先队列来解答，优先队列的原理很简单。

首先确定最后的长度，一般情况下就是给的一个参数。

之后对开始把符合条件的数据插入到数组中，没插入一次都进行排序，如果插入后到数组长度超过k，那么将数组末尾的元素去掉，进行下一次插入操作即可。

如此在所有元素都插入后即可得到最后的结果了。

笔者当时并没有想到这种解决方案，只想出了常规解决方案。

对了，这里有个前提，比较字母的顺序可以使用字符串的localeCompare()方法。

自己的答案（常规解法）

自己的答案就比较丑陋了，代码比较多。

var topKFrequent = function(words, k) {
  var obj = {}
      arr = []
  for (const word of words) {
    if (obj[word]) {
      obj[word]++
    } else {
      obj[word] = 1
      arr.push(word)
    }
  }
  arr.sort((a, b) => {
    if (obj[a] === obj[b]) return a.localeCompare(b)
    return obj[b] - obj[a]
  })
  return arr.slice(0, k)
};
复制代码

很简单逻辑，首先循环数组， 拿到一个对象和数组。对象存储着每个单词出现的次数，数组可以理解为去重之后的原单词数组。

其实仔细看会发现这个去重后的数组完全没有存在的必要，使用Object.keys(obj)完全可以拿到，最后单独的slice()也没必要，可以接在sort()后面。

所以这段代码可以简化成这样?：

var topKFrequent = function(words, k) {
  var obj = {}
  for (const word of words) {
    obj[word] = (obj[word] || 0) + 1
  }
  return Object.keys(obj)
    .sort((a, b) => obj[a] === obj[b] ? a.localeCompare(b) : obj[b] - obj[a])
    .slice(0, k)
};
复制代码

看起来清爽了很对吧，但其实还有更简单的代码，这个放在后面说。

更好的方法（优先队列）

优先队列的逻辑在解释部分有说过，这里不多赘述。

笔者翻了翻答案，并没有发现优先队列的JavaScript解法，官方也没有提供JavaScript答案，下面的解法是笔者自己写出来的，如果问题，请及时指出。

var topKFrequent = function(words, k) {
  var map = new Map()
      arr = []
  function sortArr(a, b) {
    return map.get(a) === map.get(b) ? a.localeCompare(b) : map.get(b) - map.get(a)
  }
  for (const word of words) {
    map.set(word, map.get(word) ? map.get(word) + 1 : 1)
  }
  for (const word of map.keys()) {
    arr.push(word)
    arr.sort(sortArr)
    if (arr.length > k) arr.pop()
  }
  return arr
};
复制代码

现实一个sortArr的函数，用来对数组进行排序，之后老方法拿到每个单词出现的次数，最后维护一个优先队列就完事了，很简单的代码。

更好的方法（常规解法-一行）

这是笔者看到比较有趣的一个方法，没有新增额外对象，真是一行代码就搞定了。

var topKFrequent = function(words, k) {
  return [...words.reduce((map, word) => map.set(word, (map.get(word) || 0) + 1), new Map)]
    .sort((a, b) => a[1] === b[1] ? a[0].localeCompare(b[0]) : b[1] - a[1])
    .slice(0, k)
    .map(v => v[0])
};
复制代码

初看可能有点小绕，这里拆开看。

首先看[]内部的东西?：

words.reduce((map, word) => map.set(word, (map.get(word) || 0) + 1), new Map)
复制代码

这里用的是一个reduce，最后的返回值是一个Map对象，这一步相信大家都能理解，那展开这个对象会得到什么呢？这一点笔者也有点意想不到，会得到一个二维数组?：

[
	['the', 4],
	['is', 2],
	...
]
复制代码

子数组的第一个元素是Map的key，第二个元素是value。

拿到我们想要的数组之后开始进行sort操作，完成排序后使用slice()取数组的前k个元素。

最后map一下取子数组的第一个元素就完事了。

笔者其实是不推荐一行的解题方案的，可这个答案很有意思，理解起来也很简单，推荐一下。

PS：想查看往期文章和题目可以点击下面的链接：

这里是按照日期分类的?

前端刷题路-目录（日期分类）

经过有些朋友的提醒，感觉也应该按照题型分类
这里是按照题型分类的?

前端刷题路-目录（题型分类）

有兴趣的也可以看看我的个人主页?

Here is RZ