347.前k个高频元素 中等

问题：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

输入：nums = [1], k = 1

输出：[1]

示例 3：

输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

回答：

方法一：map集合记录每个元素出现的个数，然后sort排序得到前k个元素

var topKFrequent = function(nums, k) {
    var map = new Map();
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], (map.get(nums[i]) || 0) + 1) 
    }
    var sortMap = [...map].sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(item => item[0])
    return sortMap;
};

方法二：同样map集合记录每个元素出现的次数，采用桶排序可以降低时间复杂度

var topKFrequent = function(nums, k) {
    var map = new Map();
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], (map.get(nums[i]) || 0) + 1) 
    }
    var bucket = new Array(nums.length + 1)
    for (let [key, value] of map) {
        if (!bucket[value]) {
            bucket[value] = [];
        }
        bucket[value].push(key);
    }
    let result = [];
    for (let i = bucket.length - 1; i >= 0 && result.length < k; i--) {
        if (bucket[i]) {
            result.push(...bucket[i])
        }
    }
    return result
};