巡回ソート

01 / 共通の仕組み

値が既知の範囲 [0, N] または [1, N] に収まるとき、添字そのものがポインタになる —— 各要素は自分の帰る場所をすでに知っている。 その場で順に家へ送り返してソートするか、見た添字を符号反転で記録するか。 どちらの方法でも、線形時間・定数追加領域で「欠損 / 重複 / 失われた」一連の問題が解ける。

01 / 一文での本質
値が [1, N] に収まり、どの添字が現れたかだけが 問われるとき、配列そのものがビット集合になる —— arr[|v|−1] を符号反転して 「添字 v−1 を見た」と記録する。最後にもう 1 周し、まだ正の場所が答え。
問題欠損している値を探す入力[4, 3, 2, 7, 8, 2, 3, 1]
arr
4
0
3
1
2
2
7
3
8
4
2
5
3
6
1
7
1..n
1
2
3
4
5
6
7
8
長さ 8 の配列、値は [1, 8]。次はマーク段階:各値について家のセルの符号を反転する。
ステップ
0 / 26
フェーズ
マーク
欠損
·
0 / 26

02 / パターンの骨格

# マーク段階 —— 各値の家のセルを符号反転するfor i in 0..n−1:v ← abs(arr[i])if arr[v − 1] > 0:arr[v − 1] ← −arr[v − 1]# 読み取り段階 —— まだ正の位置が欠損添字を示すfor i in 0..n−1:if arr[i] > 0: i + 1 は一度も現れていない

03 / このパターンを使うべき合図

「値は正で n を超えない」
符号反転を追加 1 ビットの安全な伝達路にする前提条件。符号が「見た」フラグを担い、 絶対値は元の値を保つ。1 つの枠、2 つの情報。
「欠損 / 重複 / 失われた値、O(1) 追加空間」
空間制約がなければハッシュ集合の方が簡単。あるからこそ、添字が唯一の合法な記憶領域になる —— 符号反転はその最も素直な使い方。
「存在の有無だけが必要、配置は不要」
各要素を実際に家へ送る必要はなく、現れた添字を復元できればよい。完全な巡回ソートよりも仕事が少ない。
「読むときは絶対値」
最初のマーク以降、配列の値はすでに負かもしれない。家の添字を求めるときは必ず v = |arr[i]| を使う —— 生の値を使うと 2 回目の訪問で家を誤って計算する。

04 / よくある落とし穴

i.
重複値で 2 度反転する。
v が 2 回現れると、素朴に符号反転すると 2 回目で家が正に戻ってしまう —— 「見た」マークが消える。反転前に if arr[v−1] > 0 でガードするか、 先に符号を読んで重複を検出する。
ii.
読み取り時に abs を忘れる。
数回マークした後の arr[i] はすでに負になりうる。家の添字を計算するときは v = |arr[i]| を使う —— 生の値だと負の領域を参照してクラッシュするか、 無関係なセルを黙って書き換える。
iii.
ゼロや範囲外の値。
この技は値が [1, n] に収まる前提。ゼロには反転すべき符号がなく、 範囲外の値には家が存在しない —— 前処理(例えば n + 1 に丸める)が必要、 さもなくばマーク段階で静かに配列が壊れる。

05 / LeetCode で練習

難易度順に 4 問。あえて解答は載せていません。

01Find All Numbers Disappeared in an Array— LC 448簡単→02Find All Duplicates in an Array— LC 442中級→03Find the Duplicate Number— LC 287中級→04First Missing Positive— LC 41難しい→

— / どれをいつ使うか

古典的巡回ソート
入力が変更可能で、各要素を物理的に正しい添字へ収めたいときに使う —— 欠損値や重複値をすべて列挙したい場合など。
家へスワップ · LC 268 · LC 448
添字マーキング
各添字が出現したか否かだけが重要で、マーク 1 周 + 読み取り 1 周で済ませたいときに使う ——arr[|x|−1] の符号を反転して「見た」を記録する。
符号反転 · LC 442 · LC 41