【LeetCode 热题100】347：前 K 个高频元素（详细解析）（Go语言版）

时间：2025-04-02 15:36:01

???? 力扣热题 347：前 K 个高频元素（详细解析）

???? 题目描述

力扣 347. 前 K 个高频元素

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

???? 示例 1：

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

???? 示例 2：

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

???? 解题思路

本题考察 高频元素统计，涉及 哈希表 和 堆（优先队列） 的应用。我们可以采用以下方法解决：

✅ 方法 1：哈希表 + 小顶堆（推荐，适用于大数据）

思路：

  1. 使用哈希表 统计每个元素的出现次数。
  2. 使用小顶堆（优先队列） 维护前 k 个高频元素，堆的大小保持在 k。
  3. 遍历哈希表，将元素插入小顶堆：
    • 如果堆的大小小于 k，直接插入。
    • 如果堆的大小等于 k，比较新元素与堆顶元素的频率，若更大则替换堆顶。

⏳ 时间复杂度分析：

  • 统计频率：O(n)
  • 堆操作：O(n log k)
  • 最终取出 k 个元素：O(k log k)
  • 总复杂度：O(n log k)，适用于大规模数据。

???? Go 实现（小顶堆）

import (
    "container/heap"
)

type Pair struct {
    num  int
    freq int
}

type MinHeap []Pair

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.(Pair)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

func topKFrequent(nums []int, k int) []int {
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }

    h := &MinHeap{}
    heap.Init(h)

    for num, freq := range freqMap {
        heap.Push(h, Pair{num, freq})
        if h.Len() > k {
            heap.Pop(h) // 保持堆大小为 k
        }
    }

    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = heap.Pop(h).(Pair).num
    }

    return result
}

✅ 方法 2：哈希表 + 快排（适用于小规模数据）

思路：

  1. 哈希表统计频率：O(n)
  2. 转化为切片后按频率排序：O(n log n)
  3. 取前 k 个元素：O(k)

⏳ 时间复杂度分析：

  • 总复杂度：O(n log n)
  • 适用于数据量较小的场景

???? Go 实现（快速排序）

import "sort"

func topKFrequentQuickSort(nums []int, k int) []int {
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }

    freqArr := make([][2]int, 0, len(freqMap))
    for num, freq := range freqMap {
        freqArr = append(freqArr, [2]int{num, freq})
    }

    sort.Slice(freqArr, func(i, j int) bool {
        return freqArr[i][1] > freqArr[j][1]
    })

    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = freqArr[i][0]
    }
    return result
}

是的，可以补充 桶排序（Bucket Sort） 作为另一种解法。桶排序适用于 元素范围较小 的情况，能够在 O(n) 线性时间内找到前 K 个高频元素。

✅ 方法 3：桶排序（Bucket Sort）

???? 思路

  1. 哈希表统计频率：用 map[int]int 统计每个元素的出现次数。
  2. 构建桶数组：创建 buckets 数组，其中索引代表元素的频率，索引值存储对应的数字。
  3. 从高频向低频遍历桶，找到前 K 个元素。

⏳ 时间复杂度分析

操作 复杂度
统计频率 O(n)
分配到桶 O(n)
遍历桶 O(n)
总复杂度 O(n)

???? Go 代码实现 

func topKFrequentBucketSort(nums []int, k int) []int {
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }

    // 创建桶，索引代表频率，存储出现该频率的数
    n := len(nums)
    buckets := make([][]int, n+1) 

    for num, freq := range freqMap {
        buckets[freq] = append(buckets[freq], num)
    }

    // 逆序遍历桶，找到前 K 个高频元素
    result := []int{}
    for i := n; i > 0 && len(result) < k; i-- {
        if len(buckets[i]) > 0 {
            result = append(result, buckets[i]...)
        }
    }

    return result[:k] // 只返回前 k 个元素
}

???? 方法对比总结

方法 时间复杂度 适用场景 备注
哈希表 + 小顶堆 O(n log k) n 很大，k 很小 适用于 大规模数据
哈希表 + 快速排序 O(n log n) n 较小，适用于静态数据 代码较简洁
哈希表 + 桶排序 O(n) n 适中，元素范围小 适用于 频率较分散的情况

???? 总结

  • ✅ 堆排序 适用于 大数据流处理，时间复杂度 O(n log k)，使用 优先队列（最小堆）。
  • ✅ 快速排序 适用于 静态数据排序，时间复杂度 O(n log n)，代码较简洁。
  • ✅ 桶排序 适用于 元素范围小且频率分散 的情况，时间复杂度 O(n)，是 最快的方法 之一。

???? 如果觉得这篇文章对你有帮助，欢迎点赞 ????、收藏 ⭐、关注 ????，持续分享更多高质量算法题解析！????????????

相关文章