座標圧縮

概要

数列 \(A_0, A_1, ..., A_{N-1}\) が与えられたときに、それぞれの要素が「全体の中で何番目に小さいか」を求めていくことを座標圧縮と呼ぶ。
例えば

A = [6, 9, 9, 2, 100]

のような数列を座標圧縮すると以下のようになる。

[1, 2, 2, 0, 3]

同じ値が複数ある場合はすべてが同じ順位を占めるとして考えるため、座標圧縮後も同じ値になる。また以降の順位も 1 つずつ値を変えるようにする。つまり以下は間違いになる。

[1, 2, 2, 0, 4]

029 - Long Bricks（★5）
上記のような問題では座標圧縮することで計算量を削減できる。

実装例

Python では辞書型を使って下記のように実装できる。

# 座標圧縮したい数列
A = [9, 3, 10, 58, 100, 39, 9, 8, 55, 1000, 0]

# 重複削除と昇順ソート
B = sorted(set(A))

# 順位付け
D = {v: i for i, v in enumerate(B)}

print(A)  # [9, 3, 10, 58, 100, 39, 9, 8, 55, 1000, 0]
print([D[a] for a in A])  # [3, 1, 4, 7, 8, 5, 3, 2, 6, 9, 0]