vvrf / DSA.log

问题拆解

给一个数组和整数 k，返回出现频率最高的 k 个元素，题目保证答案唯一，且要求优于 O(n log n)。

第一步没有悬念：哈希表统计每个数出现几次。有分歧的是第二步——按频次取前 k 个。全量排序是 O(n log n)，恰好撞在题目禁止的线上；小顶堆维护 k 个候选能到 O(n log k)，已经达标，也是数据流场景下的标准答案。

但这题还能再进一步。注意频次的取值范围天然有界：一个数最多出现 n 次。值域有界的量就能当数组下标用——按频次开 n+1 个桶，把每个数扔进它频次对应的桶里，再从高频端往回收集，凑够 k 个即止。整个过程没有比较排序，纯 O(n)。

排序之所以要 O(n log n)，是因为比较排序对值域一无所知；一旦发现待排的量有界（频次 ≤ n），计数 / 桶就能把 log 直接抹掉。

频次当下标的桶排序

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.merge(num, 1, Integer::sum);
    }
    // 桶下标 = 频次，最大频次不超过 nums.length
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i <= nums.length; i++) {
        buckets.add(new ArrayList<>());
    }
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        buckets.get(e.getValue()).add(e.getKey());
    }
    int[] result = new int[k];
    int idx = 0;
    for (int freq = nums.length; freq >= 0 && idx < k; freq--) {
        for (int num : buckets.get(freq)) {
            result[idx++] = num; // 从高频桶往低频桶收集
            if (idx == k) break;
        }
    }
    return result;
}

def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    # 桶下标 = 频次，最大频次不超过 len(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result = []
    for freq in range(len(nums), 0, -1):  # 从高频桶往低频桶收集
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

func topKFrequent(nums []int, k int) []int {
    count := map[int]int{}
    for _, num := range nums {
        count[num]++
    }
    // 桶下标 = 频次，最大频次不超过 len(nums)
    buckets := make([][]int, len(nums)+1)
    for num, freq := range count {
        buckets[freq] = append(buckets[freq], num)
    }
    result := make([]int, 0, k)
    for freq := len(nums); freq > 0 && len(result) < k; freq-- {
        for _, num := range buckets[freq] { // 从高频桶往低频桶收集
            result = append(result, num)
            if len(result) == k {
                break
            }
        }
    }
    return result
}

pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let mut count = std::collections::HashMap::new();
    for &num in &nums {
        *count.entry(num).or_insert(0usize) += 1;
    }
    // 桶下标 = 频次，最大频次不超过 nums.len()
    let mut buckets: Vec<Vec<i32>> = vec![Vec::new(); nums.len() + 1];
    for (num, freq) in count {
        buckets[freq].push(num);
    }
    let mut result = Vec::with_capacity(k as usize);
    for bucket in buckets.iter().rev() { // 从高频桶往低频桶收集
        for &num in bucket {
            result.push(num);
            if result.len() == k as usize {
                return result;
            }
        }
    }
    result
}

两个细节别踩：桶要开 n + 1 个——数组全是同一个数时频次恰好为 n，开 n 个就越界；收集必须从最高频次倒着走，正着走拿到的是频率最低的 k 个。另外同一个桶里可能装着多个频次相同的数，凑够 k 就要立刻停，题目保证答案唯一，所以不会在“取谁不取谁”上产生歧义。

如果场景换成数据一批批到来、或者 n 大到桶数组开不下，小顶堆的 O(n log k) 解法更合适：堆里始终只留 k 个候选，新频次比堆顶大就换掉堆顶——一句话的事，这里就不铺第二组代码了。

复杂度

指标	复杂度	原因
时间	`O(n)`	计数、进桶、收集各扫一遍，没有比较排序
空间	`O(n)`	哈希表加 n+1 个桶

可以迁移的模式

“按某个量排序”之前先问一句：这个量的值域有界吗？有界就考虑计数 / 桶，把 log 抹掉；
频次、年龄、评分这类天然有上限的量，最适合当数组下标；
Top-K 的两条路线要分场景：离线且值域有界用桶 O(n)，流式或 k 远小于 n 用堆 O(n log k)。

把“排序”换成“分桶”，是频次类统计题最常见的一次降维。