0347. 前 K 个高频元素【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 桶排序

1. 📝 题目描述

• leetcode

给你一个整数数组 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]

---

提示：

• 1 <= nums.length <= 10^5
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n)，其中 n 是数组大小。

2. 🎯 s.1 - 桶排序

c

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
    // 哈希表计数（简化版：先排序再统计）
    int* sorted = (int*)malloc(sizeof(int) * numsSize);
    memcpy(sorted, nums, sizeof(int) * numsSize);
    qsort(sorted, numsSize, sizeof(int), (int(*)(const void*, const void*))strcmp);
    // 统计频率
    int unique = 0, cap = numsSize;
    int* vals = (int*)malloc(sizeof(int) * cap);
    int* freqs = (int*)malloc(sizeof(int) * cap);
    for (int i = 0; i < numsSize; ) {
        int j = i;
        while (j < numsSize && sorted[j] == sorted[i]) j++;
        vals[unique] = sorted[i];
        freqs[unique] = j - i;
        unique++;
        i = j;
    }
    // 桶排序
    int** buckets = (int**)calloc(numsSize + 1, sizeof(int*));
    int* bSizes = (int*)calloc(numsSize + 1, sizeof(int));
    for (int i = 0; i < unique; i++) {
        int f = freqs[i];
        if (!buckets[f]) buckets[f] = (int*)malloc(sizeof(int) * unique);
        buckets[f][bSizes[f]++] = vals[i];
    }
    int* res = (int*)malloc(sizeof(int) * k);
    *returnSize = 0;
    for (int i = numsSize; i >= 0 && *returnSize < k; i--) {
        for (int j = 0; j < bSizes[i] && *returnSize < k; j++)
            res[(*returnSize)++] = buckets[i][j];
    }
    free(sorted); free(vals); free(freqs);
    for (int i = 0; i <= numsSize; i++) if (buckets[i]) free(buckets[i]);
    free(buckets); free(bSizes);
    return res;
}

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const map = new Map()
  for (const num of nums) map.set(num, (map.get(num) || 0) + 1)
  // 桶排序
  const buckets = new Array(nums.length + 1).fill(null)
  for (const [num, freq] of map) {
    if (!buckets[freq]) buckets[freq] = []
    buckets[freq].push(num)
  }
  const res = []
  for (let i = buckets.length - 1; i >= 0 && res.length < k; i--) {
    if (buckets[i]) res.push(...buckets[i])
  }
  return res.slice(0, k)
}

py

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in count.items():
            buckets[freq].append(num)
        res = []
        for i in range(len(buckets) - 1, -1, -1):
            res.extend(buckets[i])
            if len(res) >= k:
                return res[:k]
        return res[:k]

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• 统计频率后，以频率为索引建立桶
• 从高频桶向低频桶收集元素，直到收集到 $k$ 个