座標圧縮 (coordinate compression)

概要

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

計算量

\(O(N \log N)\)

実装

#include<map>
#include<vector>
using namespace std;


map<int, int> compress(const vector<int> &xs) {
  map<int, int> result;
  for(int i=0; i<xs.size(); ++i) {
    result[xs[i]] = 0;
  }
  int i = 0;
  for(auto it = result.begin(); it != result.end(); ++it, ++i) {
    result[(*it).first] = i;
  }
  return result;
}