座標圧縮 (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))

戻る