座標圧縮 (coordinate compression)

概要

\(N\)個の点、\(x_0, x_1, ...,x_{N-1}\)に対し、昇順に\(0, 1, ..., N-1\)を割り当てる。

計算量

\(O(N \log N)\)

実装

# 入力: 座標の配列
# 出力 MP[e] = i: 座標eはi番目に該当
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i for i, e in enumerate(XS)}

# 1行バージョン
compress2 = lambda arr: {e: i for i, e in enumerate(sorted(set(arr)))}

# 直に座標圧縮する場合
compress3 = lambda arr: list(map({e: i for i, e in enumerate(sorted(set(arr)))}.__getitem__, arr))