09. Top K Frequent Elements

読了目安 約1分

Heap / LeetCode 347 (Medium) — 出現回数の多い上位 K 種類の値を求める。

問題

LeetCode 347. Top K Frequent Elements（Medium / カテゴリ: Heap）

整数の配列 nums と整数 k が与えられます。 出現回数が多い上位 k 種類の値を返してください。 答えは一意に決まる入力だけが与えられ、返す順序は問いません（テストコードはソートして比較します）。

考え方

Swift 実装のポイント

• 辞書の sorted { $0.value > $1.value } で、キーと値のペアを回数の降順に並べられます。
• prefix(k) は要素数が k 未満でもエラーにならず、あるだけ返します。
• 面接ではソート解に加えて、最小ヒープで O(n log k) にする改善（703 の MinHeap と同じ道具）まで話せると強いです。

class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var counts: [Int: Int] = [:]
        for num in nums {
            counts[num, default: 0] += 1
        }
        return counts.sorted { $0.value > $1.value }.prefix(k).map { $0.key }
    }
}