巡回ソート
01 / 共通の仕組み
値が既知の範囲 [0, N] または [1, N] に収まるとき、添字そのものがポインタになる —— 各要素は自分の帰る場所をすでに知っている。 その場で順に家へ送り返してソートするか、見た添字を符号反転で記録するか。 どちらの方法でも、線形時間・定数追加領域で「欠損 / 重複 / 失われた」一連の問題が解ける。
01 / 一文での本質
値が [0, N] または [1, N] に収まるとき、 各要素は自分の帰る場所を知っている —— 配列を 1 周し、arr[i] が家にいなければ家へスワップする。各スワップで 1 要素が確定するので、 全体で O(N)。問題欠損している値を探す入力[3, 0, 1, 4, 2]
arr
3
0
0
1
1
2
4
3
2
4
家
0
1
2
3
4
長さ 5 の配列、値は 0..5 から 1 つだけ欠けている。各値を自分の家へ送る。
ステップ
0 / 20
フェーズ
ソート
欠損
·
0 / 20
02 / パターンの骨格
# 各要素を正しい添字に置く(範囲 [0, n−1])i ← 0while i < n:home ← arr[i]if home < n and arr[home] ≠ home:swap arr[i], arr[home]else:i ← i + 1# もう 1 周:arr[i] ≠ i の位置が欠損値を示す
03 / このパターンを使うべき合図
「値の範囲 [0, N] / [1, N]」
最も特徴的なシグナル。値域と添字域が一致し、各値が固有の正しい席を持つ。添字と値が同じ言語を話す。
「欠損 / 重複 / 失われた値を探す」
その場でソートした後、
arr[i] ≠ i の位置はそのまま「欠損値」または 「重複が居座っている場所」を意味する —— 最後の 1 周で答えが取れる。「O(N) 時間・O(1) 追加空間」
ハッシュ集合や明示的なソートを排除する制約。巡回ソートはスワップ 1 つで両方を満たす。
「入力配列を変更してよい」
このパターンは
arr をその場で並び替える。入力を保存する必要があるなら、 先にコピーするか、姉妹パターンの添字マーキングを使う。04 / よくある落とし穴
i.
スワップ直後に
i を進めてしまう。スワップ後の新しい
arr[i] もまだ家にいないかもしれない —— 進む前に再度確認する。正しい形は while (arr[i] が家にいない) swap; else i++ であって、 単純な for ループではない。ii.
[0, N] と [1, N] の規約を混同する。
値域が
[1, N] なら v の家は添字 v − 1、[0, N] なら添字 v。1 つに決めて貫く —— このパターンの境界 1 ずれはすべてここから生まれる。iii.
重複値で無限ループする。
同じ家を持つ等値が 2 つあると、スワップが堂々巡りになる。条件は
arr[i] != arr[home] にする —— i != home ではダメ。 目的の席に正解がすでに座っていれば、手を出さない。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
古典的巡回ソート
入力が変更可能で、各要素を物理的に正しい添字へ収めたいときに使う —— 欠損値や重複値をすべて列挙したい場合など。
家へスワップ · LC 268 · LC 448
添字マーキング
各添字が出現したか否かだけが重要で、マーク 1 周 + 読み取り 1 周で済ませたいときに使う ——
arr[|x|−1] の符号を反転して「見た」を記録する。符号反転 · LC 442 · LC 41