692. Top K Frequent Words

给一非空的单词列表，返回前 k 个高频单词，返回的答案按照单词出现频率由高到低排序。如果不同的单词有相同的出现频率，按字母顺序排序。

堆排序

计算每个单词的频率，将其添加到存储大小为k 的小根堆中。将频率最小的候选项放在堆的顶部，从堆中弹出最多 k 次，并反转结果。

• 时间复杂度 O(NlogK)，空间复杂度O(N)
• Runtime: 96 ms, faster than 65.75%
• Memory Usage: 45.1 MB, less than 13.72%

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function(words, k) {
    let map = new Map()
    for (let word of words) {
        if(map.has(word)) map.set(word, map.get(word) + 1)
        else map.set(word, 1)
    }
    
    let flag = 0
    let len = map.size
    let heap = []
    map.forEach((value, index) => {
        if(flag < k) {
            heap.push(index)
            if(flag === k - 1) {
                buildHeap(heap, map, k)
            }
        } else {
            if(
                map.get(heap[0]) < map.get(index)
                || 
                (map.get(heap[0]) === map.get(index) && heap[0].localeCompare(index) === 1)
            ) {
                heap[0] = index
                heapify(heap, map, 0, k)
            }
            
        }
        flag++
    })
    
    let res = []
    
    for(let i = 0; i < k; i++) {
        buildHeap(heap, map, k - i)
        res.unshift(heap.shift())
       
    }
    return res
};

// 维护小顶堆
var buildHeap = function(heap, map, k) {
    let mid = k >> 1
    for (let i = mid; i >= 0; i--) {
        heapify(heap, map, i, k)
    }
}
    

var heapify = function(heap, map, i, k) {
    let min = i
    let left = 2 * i + 1
    let right = 2 * i + 2
    if(left < k 
       && heap[left] 
       && (
        map.get(heap[min]) > map.get(heap[left])  
        || 
        (map.get(heap[min]) === map.get(heap[left])  && heap[min].localeCompare(heap[left]) === -1))
      ) min = left
    if(
        right < k 
        // && heap[right] 
        && (
            map.get(heap[min]) > map.get(heap[right]) 
            ||  
            (map.get(heap[min]) === map.get(heap[right])  && heap[min].localeCompare(heap[right]) === -1))
    ) min = right
    
    if(min > i) {
        swap(heap, min, i)
        heapify(heap, map, min, k)
    }
}

var swap = function(nums, i, j) {
    let temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

哈希表 + 排序算法

• 时间复杂度 O(NlogN)， 空间复杂度O(N)，Array.sort()方法的时间复杂度一般为O(NlogN)，深入浅出 JavaScript 的 Array.prototype.sort 排序算法

• Runtime: 96 ms, faster than 65.75%

• Memory Usage: 43.8 MB, less than 40.45%

var topKFrequent = function(words, k) {
    if(!words.length) return []
    const map = {}
    words.forEach(word => map[word]? map[word]++ : (map[word] = 1))
    return Object.keys(map).sort((a, b) => map[b] - map[a] || a.localeCompare(b)).slice(0, k)
};