coordinate compression

座標圧縮について

タグ binary-search

  • データサイエンスのrankに該当する概念
  • 二分探索を使うことでO(n log n)する

pythonによる例

import bisect
L = [55, 6, 432, 55, 98, 67, 6, 32]

v = sorted(list(set(L)))

rank = []
for l in L:
    rank.append(bisect.bisect_left(v, l))

print(L)
print(rank)

$ python3 a.py
[55, 6, 432, 55, 98, 67, 6, 32]
[2, 0, 5, 2, 4, 3, 0, 1]