NISHIO Hirokazu[Translate]
逆写像テーブル
f(x) = yが与えられてg(y) = xを作る
python
for x in all_x: g[f[x]] = x

線形オーダーの前処理で、yからxへの写像が定数オーダーになる

注意点
yの値域が大きい時に配列だとメモリエラーになりうる
ハッシュテーブルが一つの選択肢
ソートして二分探索という選択肢も
前処理がNlogN、取得がlogNになっちゃうけど。
同じyの値を取るxがあると復元できない
単射であることが必要
全射でない時は「対応するxがない」ということを表現するための値と、その値かどうかのチェックが必要

Related Pages

"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]