Сжатие координат

Часто бывает полезно преобразовать последовательность чисел либо каких-то других объектов в промежуток последовательных целых чисел — например, чтобы использовать её элементы как индексы в массиве либо какой-нибудь другой структуре.

Эта задача эквивалентна нумерации элементов множества, что можно сделать за $O(n)$ через хеш-таблицу:

vector<int> compress(vector<int> a) {
    unordered_map<int, int> m;

    for (int &x : a) {
        if (m.count(x))
            x = m[x];
        else
            m[x] = m.size();
    }

    return a;
}

Элементам будут присвоены номера в порядке их первого вхождения в последовательность. Если нужно сохранить порядок, присвоив меньшим элементам меньшие номера, то задача становится чуть сложнее, и её можно решить разными способами.

Как вариант, можно отсортировать массив, а затем два раза пройтись по нему с хэш-таблицей — в первый раз заполняя её, а во второй раз сжимая сам массив:

vector<int> compress(vector<int> a) {
    vector<int> b = a;
    sort(b.begin(), b.end());

    unordered_map<int, int> m;

    for (int x : b)
        if (!m.count(x))
            m[x] = m.size();

    for (int &x : a)
        x = m[x];

    return a;
}

Также можно выкинуть из отсортированного массива дупликаты (за линейное время), а затем использовать его для нахождения индекса каждого элемента исходного массива бинарным поиском:

vector<int> compress(vector<int> a) {
    vector<int> b = a;

    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    for (int &x : a)
        x = int(lower_bound(b.begin(), b.end(), x) - b.begin());

    return a;
}

Оба подхода работают за $O(n \log n)$. Используйте тот, который больше нравится.