347.前K个高频元素

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
    // 哈希表记录每个元素出现次数
    let map = new Map()

    // 先统计每个元素出现的次数
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], (map.get(nums[i]) || 0) + 1)
    }
    console.log(map,Array.from(map))

    // 把元素出现频率组成一个数组，然后进行排序
    // 同时预先记录某个频率对应的元素
    let cntArr = []
    let cnt2num = new Map()
    for (let [num, cnt] of map) {
        cntArr.push(cnt)
        if (cnt2num.has(cnt)) {
            let numArr = cnt2num.get(cnt)
            numArr.push(num)
            cnt2num.set(cnt, numArr)
        } else {
            cnt2num.set(cnt, [num])
        }
    }
    // console.log(cntArr)
    // console.log(cnt2num)

    // 对频率数组排序倒序，使用桶排序，时间复杂度O(n)
    const sortedCntArr = bucketSort(cntArr)
    // console.log(sortedCntArr)

    // 返回前k高频率的元素
    let res = []
    for (let i = 0; i < k; i++) {
        let numArr = cnt2num.get(sortedCntArr[i])
        res = res.concat(numArr)
    }

    // 里面有可能有重复元素，用set去重
    return [...new Set(res)]
};

/**
 * 桶排序
 * @param {number[]} arr 
 */
function bucketSort(arr) {
    // 1.确定桶的容量，一般使用数组的长度
    const bucketSize = arr.length
    // 2.确定最大值最小值
    const min = Math.min(...arr)
    const max = Math.max(...arr)
    // 3.确定桶的数量
    const bucketCount = Math.floor((max - min) / bucketSize) + 1
    // 4.初始化桶
    const buckets = new Array(bucketCount).fill(0).map(() => [])
    // 6.将元素分配到桶里
    for (let i = 0; i < arr.length; i++) {
        // 分配到pos号桶
        const pos = Math.floor((arr[i] - min) / bucketSize)
        buckets[pos].push(arr[i])
    }
    // 7.对每个桶的元素进行升序排序
    for (let i = 0; i < buckets.length; i++) {
        buckets[i].sort((a, b) => a - b)
    }
    // 8.合并桶
    let res = []
    for (let i = 0; i < buckets.length; i++) {
        res = res.concat(buckets[i])
    }
    // 9.升序直接返回res，要到序的返回res.reverse()
    return res.reverse()
}

// console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2))
console.log(topKFrequent([1, 2], 2))