🚀 力扣熱題 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  intfreq int
}type MinHeap []Pairfunc (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 := *hn := 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)，是 最快的方法 之一。

---

💡 如果覺得這篇文章對你有幫助，歡迎點贊 👍、收藏 ?、關注 💻，持續分享更多高質量算法題解析！🎯🚀📌