347.前 K 个高频元素

前 K 个高频元素

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= $10^5$
• $-10^4$ <= nums[i] <= $10^4$
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一

解析

桶排序：以频率为下标建桶，将相同频率的数字放在同一个桶中。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  // 桶排序：buckets[i] 存储频率为 i 的元素
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, freq] of freqMap) {
    buckets[freq].push(num);
  }

  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
};

桶排序法：时间复杂度 O(n)，从高频到低频遍历桶，取前 k 个即可。