🚀 力扣热题 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：哈希表 + 小顶堆（推荐，适用于大数据）
思路：
- 使用哈希表 统计每个元素的出现次数。
- 使用小顶堆（优先队列） 维护前
k个高频元素，堆的大小保持在k。 - 遍历哈希表，将元素插入小顶堆：
- 如果堆的大小小于
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：哈希表 + 快排（适用于小规模数据）
思路：
- 哈希表统计频率：O(n)
- 转化为切片后按频率排序：O(n log n)
- 取前
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）
💡 思路
- 哈希表统计频率：用
map[int]int统计每个元素的出现次数。 - 构建桶数组：创建
buckets数组，其中索引代表元素的频率，索引值存储对应的数字。 - 从高频向低频遍历桶，找到前
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)，是 最快的方法 之一。
💡 如果觉得这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、关注 💻，持续分享更多高质量算法题解析！🎯🚀📌
