Top K Frequent Elements (Heap + HashMap)

LC 347 題意

• 給定一個整數陣列 nums，回傳出現頻率最高的前 k 個元素。
• Ex.
  Input: nums = [1,1,1,2,2,3], k = 2
  Output: [1,2]

thoughts

• HashMap 計數每個元素出現次數。
• 使用 Min-Heap 根據頻率排序，只保留前 k 項。
• 輸出 heap 中的元素。

Kotlin

import java.util.PriorityQueue

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val freq = mutableMapOf<Int, Int>()
        for (num in nums) freq[num] = freq.getOrDefault(num, 0) + 1
        
        val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
        for ((num, count) in freq) {
            pq.offer(Pair(num, count))
            if (pq.size > k) pq.poll()
        }

        return pq.map { it.first }.toIntArray()
    }
}

Follow-up

• 若資料量很大無法放入記憶體？（→ 使用 Streaming + Heap）
• 若要找 Top K Least Frequent？（→ 換排序條件）
• 可否用 Bucket Sort 降低到 O(n)？（→ 是的，若範圍有限）