給定整數陣列
nums和整數k，回傳出現頻率最高的k個元素，回傳順序不限。題目保證答案唯一，且k在有效範圍內。要求時間複雜度優於 O(n log n)。
Example:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Intuition
TIP
核心思路：先統計頻率，再用「比 O(n log n) 更快的方式」找出前 k 高頻元素——Bucket Sort 或 Min Heap。
- 第一步都是用 HashMap 統計每個元素的出現次數
- 關鍵在於如何高效地從頻率中選出前 k 名
- Bucket Sort 利用「頻率最大為 n」的特性，用索引作為頻率桶
Approaches
1. Min Heap (Priority Queue) — O(n log k) / O(n)
- Idea: 維護一個大小為 k 的最小堆，遍歷所有頻率，堆滿後若當前頻率大於堆頂就替換
- Time:
O(n log k)- 統計 O(n)，每次堆操作 O(log k) - Space:
O(n)- HashMap 和堆
class Solution {
fun topKFrequent(nums: IntArray, k: Int): IntArray {
val freqMap = HashMap<Int, Int>()
for (num in nums) freqMap[num] = freqMap.getOrDefault(num, 0) + 1
// Min Heap：按頻率排序，堆頂是頻率最小的
val heap = java.util.PriorityQueue<Int>(compareBy { freqMap[it] })
for (num in freqMap.keys) {
heap.add(num)
if (heap.size > k) heap.poll()
}
return heap.toIntArray()
}
}⭐ 2. Bucket Sort — O(n) / O(n)
- Idea: 建立大小為 n+1 的桶陣列，索引代表頻率，將元素放入對應頻率的桶中，再從高頻桶往低頻桶收集 k 個元素
- Time:
O(n)- 統計、建桶、收集皆為線性 - Space:
O(n)- 桶陣列和 HashMap
class Solution {
fun topKFrequent(nums: IntArray, k: Int): IntArray {
val freqMap = HashMap<Int, Int>()
for (num in nums) freqMap[num] = freqMap.getOrDefault(num, 0) + 1
// bucket[i] 存放出現 i 次的所有元素
val bucket = Array(nums.size + 1) { mutableListOf<Int>() }
for ((num, freq) in freqMap) {
bucket[freq].add(num)
}
val result = mutableListOf<Int>()
for (i in bucket.lastIndex downTo 0) {
for (num in bucket[i]) {
result.add(num)
if (result.size == k) return result.toIntArray()
}
}
return result.toIntArray()
}
}Note: Quickselect (avg O(n))
Quick Select 演算法可以在平均 O(n) 時間找到第 k 大的元素，但最壞情況為 O(n^2)，且實作較複雜。Bucket Sort 在此題中更實用。
class Solution {
fun topKFrequent(nums: IntArray, k: Int): IntArray {
val freqMap = HashMap<Int, Int>()
for (num in nums) freqMap[num] = freqMap.getOrDefault(num, 0) + 1
val uniqueNums = freqMap.keys.toIntArray()
fun partition(left: Int, right: Int, pivotIdx: Int): Int {
val pivotFreq = freqMap[uniqueNums[pivotIdx]]!!
uniqueNums[pivotIdx] = uniqueNums[right].also { uniqueNums[right] = uniqueNums[pivotIdx] }
var storeIdx = left
for (i in left until right) {
if (freqMap[uniqueNums[i]]!! > pivotFreq) {
uniqueNums[storeIdx] = uniqueNums[i].also { uniqueNums[i] = uniqueNums[storeIdx] }
storeIdx++
}
}
uniqueNums[storeIdx] = uniqueNums[right].also { uniqueNums[right] = uniqueNums[storeIdx] }
return storeIdx
}
var left = 0
var right = uniqueNums.size - 1
while (left <= right) {
val pivotIdx = partition(left, right, left + (right - left) / 2)
when {
pivotIdx == k - 1 -> return uniqueNums.sliceArray(0 until k)
pivotIdx < k - 1 -> left = pivotIdx + 1
else -> right = pivotIdx - 1
}
}
return uniqueNums.sliceArray(0 until k)
}
}🔑 Takeaways
- Pattern: Top-K 問題 -> Bucket Sort（當範圍有限）或 Heap（通用）
- Key trick: 當值的範圍有上界（此題頻率最大為 n），Bucket Sort 可以達到 O(n) 線性時間，比 Heap 的 O(n log k) 更優