692-前k个高频单词-medium-哈希表排序/优先队列

给一非空的单词列表，返回前 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）
链接：https://leetcode-cn.com/problems/top-k-frequent-words

思路：
哈希表+排序：使用map保存每个单词出现次数，进行排序，取前k个即可。
优先队列：使用map保存每个单词出现次数，维护一个长度为k的最小堆，长度大于k时，出队堆顶元素即k个单词中频率最低的，就能保证最小堆中是前k个高频单词。出队时是按小到大返回前k个高频单词，所以需要反向。
复杂度分析：
哈希表+排序对长度为n的数组排序，时间复杂度为O(nlogn)，空间复杂度O(n)
优先队列将n个单词加入优先队列，添加每个单词的复杂度是logk，弹出单词时复杂度是k，k远小于n，所以时间复杂度O(nlogk) ，空间复杂度O(n)
优先队列-priority queue

//哈希表 + 排序
var topKFrequent = function(words, k) {
    const map = new Map();
    words.map(word=>{
        const cnt = map.get(word) || 0;
        map.set(word,cnt+1);
    })
    const arr = [...map.keys()];
    arr.sort((a,b)=>{
        if(map.get(a) === map.get(b)){
            return a > b ? 1 : -1;//因为 sort是按-1/0/1来处理 直接 a>b 会把boolean结果转成数字 即永远不会出现 -1 这个比较结果
            //return a.localeCompare(b);  使用localeCompare函数也可完成比较
        }else{
            return map.get(b) - map.get(a);
        }
    })
    return arr.slice(0,k);
};
//优先队列
var topKFrequent = function(words, k) {
  const map = new Map();
  words.map(word => {
    const cnt = map.get(word) || 0;
    map.set(word, cnt + 1);
  });
  const pq = new PriorityQueue((a, b) => {
    if (map.get(a) === map.get(b)) {
      return a > b ;
    } else {
      return map.get(a) < map.get(b);
    }
  });
  const arr = [...map.keys()];
  arr.map((keyword) => {
    pq.push(keyword);
    if (pq.size() > k) {
      pq.pop();
    }
  });
  const result = [];
  while (!pq.empty()) {
    result.push(pq.pop());
  }
  //需要注意因将数组反向，因为维护的是最小堆，每次出队的是最小的，所以需要逆序
  return result.reverse();
};

692-前k个高频单词-medium-哈希表 排序/优先队列