座標圧縮
Abstract
値の大きさの順序にだけ興味があるときや, 位置関係のみに興味があるときなどに利用するテクニック.
Explanation
TODO 書く.
Implementation
列に関する座標圧縮なら, 例えば, 以下のような実装ができる.
Input
長さ$ Nのリスト A
Output
座標圧縮後のリスト
Procedure
1. リスト A の重複を除去する (Pythonなら set を使えばできる).
2. 重複を除いた後の A を昇順にソートし, 各要素が何番目の要素かを B[a] に記録する (B は dict を利用するとよい).
3. リスト A の各要素 a を B[a] に変換したリストを出力する.
Time complexity
$ O(N \log N) time.手順2のソートがボトルネック.
code:python
def coord_compress(A):
B = {a: i for i, a in enumerate(sorted(set(A)))}
Verification
References