347. Top K Frequent Elements

给定一个非空的整数数组，返回其中出现频率前k高的元素。时间复杂度需要优于 O(NlogN)，数组中前 k 个高频元素的集合是唯一的。

哈希 + 小顶堆

遍历整个数组，使用哈希表记录每个数字出现的次数。遍历 map，将前 k 个数，构造一个小顶堆，从 k 为开始，继续遍历 map，每一个数据出现的频率和小顶堆元素出现的频率进行比较，如果小于堆顶元素，则不作任何处理，如果大于堆顶元素，将这个元素替换掉堆顶元素，再堆化成一个小顶堆。遍历完成后，堆中的数据就是前 k 大的数据。

• 时间复杂度 O(nlogk)，空间复杂度O(n)
• Runtime: 100 ms, faster than 57.78%
• Memory Usage: 42.8 MB, less than 38.23%

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = new Map()
    nums.forEach(i => {
        if(map.has(i)) {
            map.set(i, map.get(i) + 1)
        } else {
            map.set(i, 1)
        }
    })
    if(map.size <= k) {
        return [...map.keys()]
    }
     console.log(map)
    let len = 0
    let heap = []
    map.forEach((value, key) => {
        if (len < k) {
            heap.push(key)
            if(len === k - 1) buildHeap(heap, map, k)            
        } else {
            if(map.get(heap[0]) < value) {
                heap[0] = key
                heapify(heap, 0, k, map)
            }
        }
        len++
    })   
    
    return heap
};

 
let buildHeap = function(heap, map, boundary) {
    if(boundary < 2) return heap
    let mid = (boundary - 1) >> 1
    for (let i = mid; i >= 0; i--) {
        heapify(heap, i, boundary, map)
    }    
}

let heapify = function(heap, index, boundary, map) {
    let min = index
    let left = 2 * index + 1
    let right = 2 * index + 2
    if(left < boundary && map.get(heap[left]) < map.get(heap[min])) {
        min = left
    }
    
    if(right < boundary && map.get(heap[right]) < map.get(heap[min])) {
        min = right
    }
    
    if(min > index) {
        swap(heap, min, index)
        heapify(heap, min, boundary, map)
    }
}

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

桶排序

原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序。

• 使用map 存储频率
• 创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可
• 时间复杂度 O(n)，空间复杂度O(n)
• Runtime: 96 ms, faster than 70.24%
• Memory Usage: 42.5 MB, less than 41.49%

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = new Map()
    for (let e of nums) {
        if(map.has(e)) map.set(e, map.get(e) + 1)
        else map.set(e, 1)
    }
    if(map.size <= k) return [...map.keys()]
    return bucketSort(map, k)
};

var bucketSort = function(map, k) {
    let bucket = []
    let res = []
    map.forEach((value, key) => {
        if(!bucket[value]) bucket[value] = [key]
        else bucket[value].push(key)
    })
    
    const len = bucket.length
    for(let i = len - 1; i >= 0 && res.length < k; i--) {
        if(bucket[i]) res.push(...bucket[i])
    }
    return res
}