このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は
#noredirect を付けた URL /coordinate-compression#noredirect を利用してください。
- name
- 座標圧縮
- short description
- 座標圧縮とは、与えられた長さ $N$ の整数列 $a$ から、長さ $N$ の自然数列 $b$ であって要素の順序関係が $a$ と同じでかつ最大値 $\max_i b_i$ が最小であるような $b$ を作ること。ただし「要素の順序関係が同じ」とは、任意の $i, j$ に対し $a_i \le a_j \leftrightarrow b_i \le b_j$ を満たすことを言う。このような $b$ は常に一意に存在し、単純な方法により $O(N \log N)$ で構成できる。
- input
- 長さ $N$ の整数列 $a$
- output
- 長さ $N$ の自然数列 $b$ であって、要素の順序関係が $a$ と同じでかつ最大値 $\max_i b_i$ が最小であるもの
- time complexity
- $O(N \log N)$
- changelog
-
- 2021年02月05日「見出し作成」 authors: kimiyuki, reviewers:none
- license
This work is licensed under a Creative Commons Attribution 4.0 International License.