目次
全体像（アプローチ）
- 頻度表（count）を作る：各値の出現回数を数える。
- 頻度ごとの“バケット”（freq）を作る：
freq[c]に「出現回数がcの値たち」を入れる。 - 高頻度バケットから順に拾う：
freqを 大きい頻度→小さい頻度 の順に走査し、要素を集めてk個になったら返す。
ポイントは、最大頻度が len(nums) を超えないこと。よって長さ len(nums)+1 の配列（インデックス 0 は未使用）を用意すれば、「頻度→要素群」の逆引き表が O(n) で構築でき、ソート不要です。
コード全体
func topKFrequent(nums []int, k int) []int {
count := make(map[int]int)
freq := make([][]int, len(nums)+1)
for _, num := range nums {
count[num]++
}
for num, cnt := range count {
freq[cnt] = append(freq[cnt], num)
}
res := []int{}
for i := len(freq) - 1; i > 0; i-- {
for _, num := range freq[i] {
res = append(res, num)
if len(res) == k {
return res
}
}
}
return res
}
各行の役割・処理の流れ
1) 出現頻度を数える
count := make(map[int]int)
for _, num := range nums {
count[num]++
}
count[num]++で回数をインクリメント。map[int]intはキー未登録ならゼロ値（0）から始まるのでそのまま++可能。
2) “頻度→要素群” のバケットを構築
freq := make([][]int, len(nums)+1)
for num, cnt := range count {
freq[cnt] = append(freq[cnt], num)
}
freq[c]は「頻度が c 回の整数のリスト」。- 配列長を
len(nums)+1にするのは、最大頻度が配列長（=入力長） だから（0は実質未使用）。
バケットソート
何をするアルゴリズム？
入力データの値域（分布）を利用して、値の範囲ごとに“バケツ（bucket）”へ振り分け、各バケツを個別に整列し、最後にバケツ順に連結して全体を整列する手法です。
鍵は「値がある範囲に均等に分布している」という仮定（またはそれに近い性質）。
いつ使う？
- 値が実数や連続値で、ある区間にほぼ一様分布する（例：0.0〜1.0 の小数）
- 値域が分かっていて、バケツ分割がうまくいく
- 内部の小さな整列で済むため、平均的に線形時間を期待できる
一様分布に近いほど効果的。偏りが大きいと一部のバケツが重くなり、効果が落ちます。
基本ステップ
- バケツを用意：値域を等間隔（または問題に合わせた規則）で分割して B 個のバケツを作る。
- 振り分け：各要素を対応するバケツへ入れる（
index = f(value)）。 - バケツ内整列：各バケツの中を通常の比較ソート（挿入ソート・クイックソートなど）で整列。
- 連結：バケツのインデックス順に順番に結合して完成。
計算量の目安
- 平均：O(n + B) + 各バケツ内の整列（期待的に O(n) に近い）
- 一様分布で、各バケツのサイズが n/B 程度に均されると、総コストは概ね O(n)。
- 最悪：O(n log n)（極端に偏って1つのバケツに集まった場合）
- 空間：O(n + B)
似たアルゴリズムとの違い
- カウントソート：
整数の離散値に対して頻度配列を作る。値域が広いと配列が巨大になる。安定に O(n + K)。
⇒ バケットソートは連続値や実数も扱いやすい（バケツ内を比較ソート）。 - 基数ソート（Radix）：
桁ごとに安定なソート（多くはカウントソート）を繰り返す。整数・文字列に強い。
⇒ バケットは分布活用型、Radixは桁構造活用型。 - ヒープソート：
比較ソートで常に O(n log n)。分布を使わない。
3) 高頻度から拾って k 個返す
res := []int{}
for i := len(freq) - 1; i > 0; i-- { // 高頻度→低頻度
for _, num := range freq[i] {
res = append(res, num)
if len(res) == k {
return res
}
}
}
return res
iを末尾（最大頻度）から下げていき、freq[i]に入っている値を順番にresに追加。k個集まったら即返すので無駄がない。
この解法の計算量とメモリ量
- 時間計算量：
- カウント
O(n) - バケット詰め
O(U)（Uはユニーク要素数、U ≤ n） - 逆走査で拾う
O(n)（最悪でも合計で各要素一度ずつ見る）
→ 合計 O(n)（漸近的に線形）
- カウント
- 追加メモリ：
countに O(U)freqに O(n)（各要素がいずれか1つのバケットに入る）
→ 合計 O(n)
使っている主な言語機能（import不要の組み込み）
make(map[int]int)：書き込み可能なmapを初期化（nil map での書き込みは panic）。make([][]int, len)：スライスのスライスを作成（各内側スライスはnilで、appendで延びる）。range：スライス・マップの反復。append：スライス末尾に要素を追加。必要に応じて容量が自動拡張。- ゼロ値の有効活用：
mapの未登録キーは 0、スライスはnilでもappend可。
エッジケースと注意点
k == 0：空スライスを返すのが自然（必要なら先頭でガード）。k > ユニーク数：このコードは「存在するだけ返す」挙動（resはk未満でも返る）。要件次第でmin(k, len(count))に調整しても良い。- 順序の安定性：同頻度内の順序は 入力順には依存しない（バケットに push された順）。安定順序が必要なら別管理が必要。
- メモリ上限：
freqは長さn+1なので、nが非常に大きい場合にメモリ使用量が増える。とはいえ各要素はどれか1つのバケットにしか入らないため、総計はおおむねO(n)に収まる。
ヒープ解法との使い分け（比較）
| 観点 | バケット法（この実装） | ヒープ法（Min-Heap） |
|---|---|---|
| 時間計算量 | O(n) | O(n log k) |
| メモリ | O(n) | O(n + k) |
| 実装の短さ | 短い（ライブラリ不要） | 少し長い（container/heap 実装 or 外部PQ） |
| 向いている状況 | n が大きくても一括で処理できる時 | k がかなり小さく、n が巨大な時 |
| 安定順序 | なし | なし（工夫すれば可） |
実務では
kが小さい＆nが巨大 ならヒープ、素直に速く書きたい ならバケットがラク、ということが多いです。
ミニ例での動き
nums = [1,1,1,2,2,3], k = 2
count→{1:3, 2:2, 3:1}freq[3] = [1],freq[2] = [2],freq[1] = [3]- 高頻度から見る：
i=6..1のうちi=3→[1]→res=[1]、i=2→[2]→res=[1,2]→k=2到達で返す → [1,2]
まとめ
- 頻度ごとのバケットを作って、高頻度から順に拾うだけの線形時間アルゴリズム。
- 最大頻度が
nを超えない性質を利用し、ソート不要で O(n) を実現。 - Goの組み込み（
make,append,range）だけでシンプルに書けるのが強みです。
コメント