LeetCode LCR 060. 前 K 个高频元素

Categories:

题目描述
思路分析
1. 解法一：哈希计数 + 小顶堆（推荐）
2. 解法二：桶排序
相似题目

题目描述

✅ LCR 060. 前 K 个高频元素

思路分析

解法一：哈希计数 + 小顶堆（推荐）

核心思路：

用哈希表统计每个元素出现的频次，时间 O(n)

维护大小为 k 的小顶堆（按频次升序），遍历频次表时将元素入堆

堆大小超过 k 时弹出堆顶（频次最小的），保证堆中始终是当前频次最高的 k 个元素

遍历结束后堆中剩余的 k 个元素即为答案

复杂度分析：

时间复杂度：O(n log k)，其中 n 为数组长度，每次堆操作为 O(log k)

空间复杂度：O(n + k)，其中 n 为哈希表大小，k 为堆大小

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计每个元素的出现频次
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.merge(num, 1, Integer::sum);
        }
        // 小顶堆：按频次升序，堆顶为频次最小的元素
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            heap.offer(new int[]{e.getKey(), e.getValue()});
            // 堆大小超过 k 时弹出频次最小的元素
            if (heap.size() > k) {
                heap.poll();
            }
        }
        // 收集堆中剩余的 k 个高频元素
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = heap.poll()[0];
        }
        return res;
    }
}

type Item struct {
    num  int
    freq int
}

type MinHeap []Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].freq < h[j].freq }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(Item))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func topKFrequent(nums []int, k int) []int {
    // 统计每个元素的出现频次
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }

    // 维护大小为 k 的小顶堆
    h := &MinHeap{}
    heap.Init(h)
    for num, freq := range freqMap {
        heap.Push(h, Item{num, freq})
        // 堆大小超过 k 时弹出频次最小的元素
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    // 收集堆中剩余的 k 个高频元素
    res := make([]int, k)
    for i := k - 1; i >= 0; i-- {
        res[i] = heap.Pop(h).(Item).num
    }
    return res
}

解法二：桶排序

核心思路：

统计频次后，以频次为下标建桶，数组长度为 n+1（频次最大为 n）

频次为 f 的元素加入 bucket[f] 对应的列表

从高频到低频遍历桶，依次收集元素直到凑够 k 个，无需排序

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，统计频次和遍历桶均为 O(n)

空间复杂度：O(n)，哈希表和桶数组均为 O(n)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计每个元素的出现频次
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.merge(num, 1, Integer::sum);
        }
        // 以频次为下标建桶，频次最大为 nums.length
        List<Integer>[] bucket = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            int f = e.getValue();
            if (bucket[f] == null) {
                bucket[f] = new ArrayList<>();
            }
            bucket[f].add(e.getKey());
        }
        // 从高频到低频遍历桶，收集前 k 个高频元素
        int[] res = new int[k];
        int idx = 0;
        for (int f = bucket.length - 1; f >= 0 && idx < k; f--) {
            if (bucket[f] != null) {
                for (int num : bucket[f]) {
                    res[idx++] = num;
                    if (idx == k) {
                        break;
                    }
                }
            }
        }
        return res;
    }
}

func topKFrequent(nums []int, k int) []int {
    // 统计每个元素的出现频次
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }

    // 以频次为下标建桶，频次最大为 len(nums)
    bucket := make([][]int, len(nums)+1)
    for num, freq := range freqMap {
        bucket[freq] = append(bucket[freq], num)
    }

    // 从高频到低频遍历桶，收集前 k 个高频元素
    res := make([]int, 0, k)
    for f := len(bucket) - 1; f >= 0 && len(res) < k; f-- {
        res = append(res, bucket[f]...)
    }
    return res[:k]
}

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	堆、快速选择
692. 前K个高频单词	中等	堆、哈希表
973. 最接近原点的 K 个点	中等	堆、快速选择
703. 数据流中的第 K 大元素	简单	小顶堆维护 Top-K
451. 根据字符出现频率排序	中等	哈希表、桶排序
1636. 按照频率将数组升序排序	简单	哈希表、排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/71560461