Убираем повторы прямо в массиве

У тебя есть отсортированный список, в котором часть значений повторяется: [1, 1, 2, 3, 3]. Нужно оставить каждое значение по одному разу: [1, 2, 3]. Порядок тот же, повторов нет.

Самый простой способ: завести новый список и скопировать туда нужные числа. Это работает, но памяти уходит вдвое больше. Какое-то время оба списка лежат в памяти одновременно. Если список огромный или это буфер (участок памяти под данные), который используют заново тысячи раз в секунду, на вторую копию памяти может не хватить.

Отсортированный порядок помогает. В таком списке одинаковые числа всегда стоят рядом. Поэтому можно переписать тот список, который уже есть, и почти не тратить лишнюю память.

В отсортированном списке повторы стоят рядом. Нужно по одному экземпляру каждого значения, и записать их надо в тот же список.

Ты идёшь по списку слева направо и смотришь на каждое число. Число новое, если оно отличается от предыдущего. Новое число ты переписываешь в начало списка, на первое свободное место. Повтор просто пропускаешь.

На [1, 1, 2, 3, 3] это выглядит так. Первую 1 оставляешь. Вторую 1 пропускаешь. 2 записываешь на второе место, 3 на третье. Последнюю 3 пропускаешь. Начало списка теперь 1, 2, 3, и второй список не понадобился.

Возьми два маркера. Оба идут в одну сторону, но с разной скоростью. Быстрый маркер чтения (read) смотрит на каждый элемент. Медленный маркер записи (write) помнит, куда встанет следующее оставленное значение.

Список отсортирован, поэтому значение новое ровно тогда, когда оно отличается от соседа слева. Значит, read сравнивает текущее значение с предыдущим элементом. Если значение новое, скопируй его в ячейку write и сдвинь write на шаг вперёд. Если это повтор, пропусти его: вперёд двигается только read.

В уроке 19 два маркера сходились с разных концов. Здесь оба идут слева направо. Медленный маркер показывает, куда писать, и границей поиска не служит.

Проследим на [1, 1, 2, 3, 3]. Начинаем с write = 1: первый элемент всегда остаётся.

• read=1: 1 == 1, это повтор, пропускаем.
• read=2: 2 != 1, пишем 2 в ячейку 1, write становится 2. Массив: [1, 2, 2, 3, 3].
• read=3: 3 != 2, пишем 3 в ячейку 2, write становится 3. Массив: [1, 2, 3, 3, 3].
• read=4: 3 == 3, это повтор, пропускаем.

Первые 3 ячейки: [1, 2, 3]. Новая длина 3. В ячейках 3 и 4 остались старые значения, их никто не проверяет.

Время O(n): read проходит каждый элемент один раз, а write движется только вперёд. Память O(1): список переписывается внутри себя, без дополнительной структуры.

Можно было бы складывать каждое оставленное значение в хеш-множество (Set из урока про множества) и собирать список из него. Время тоже O(n), но памяти уходит O(n). На отсортированном входе это лишняя трата: сравнение с предыдущим элементом даёт всё то же, что дало бы множество.

Системы аналитики получают события от системы доставки «хотя бы один раз». Такая доставка гарантирует, что событие дойдёт, но иногда присылает его дважды. Перед отправкой дальше отсортированный буфер событий чистят от повторов на месте. Базы данных при уплотнении (компакции) выбрасывают строки, помеченные на удаление. Команда uniq убирает повторы из отсортированного потока строк. Везде, где отсортированный буфер надо сжать без второго буфера, работает указатель записи. Чаще всего это горячий путь, то есть код, который выполняется очень часто.