Здравствуйте, товарищи, давно не виделись! 🦖
Сегодня у нас на разборе такая тема как Сжатие координат.

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

Эта задача эквивалентна нумерации элементов множества, что можно сделать за 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)

Практика
Площадь прямоугольников
Прямоугольное деление
Закраска прямой - 2
Бал

Пишите в комментарии, какую тему нам разобрать следующей😎


@postupashki_prog