347. Top K Frequent Elements

Medium

Description

給定整數陣列 nums 和整數 k，回傳出現頻率最高的 k 個元素，回傳順序不限。題目保證答案唯一，且 k 在有效範圍內。要求時間複雜度優於 O(n log n)。

Example:

Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]

Intuition#

核心思路：先統計頻率，再用「比 O(n log n) 更快的方式」找出前 k 高頻元素——Bucket Sort 或 Min Heap。

第一步都是用 HashMap 統計每個元素的出現次數
關鍵在於如何高效地從頻率中選出前 k 名
Bucket Sort 利用「頻率最大為 n」的特性，用索引作為頻率桶

Approaches#

1: Min Heap (Priority Queue)#

概念: 維護一個大小為 k 的最小堆，遍歷所有頻率，堆滿後若當前頻率大於堆頂就替換
時間複雜度: O(n log k) - 統計 O(n)，每次堆操作 O(log k)
空間複雜度: 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#

概念: 建立大小為 n+1 的桶陣列，索引代表頻率，將元素放入對應頻率的桶中，再從高頻桶往低頻桶收集 k 個元素
時間複雜度: O(n) - 統計、建桶、收集皆為線性
空間複雜度: 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()
    }
}

補充：Quick Select（平均 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（通用）
關鍵技巧: 當值的範圍有上界（此題頻率最大為 n），Bucket Sort 可以達到 O(n) 線性時間，比 Heap 的 O(n log k) 更優