Удаление дубликатов на месте

Дан отсортированный массив. Оставьте по одной копии каждого значения, не используя дополнительный массив. Обработка на месте экономит память и является классической задачей на собеседованиях. 🧹

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

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

Представляйте медленный указатель как позицию записи: всё, что находится на нём или перед ним, уже очищено от дубликатов и содержит уникальные значения.

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

Если a[fast] равно a[slow], это повтор, поэтому ничего не делайте, кроме продвижения fast. Дубликат будет незаметно пропущен.

Когда a[fast] отличается, сдвиньте медленный указатель вперёд и скопируйте туда новое значение. Так старые дубликаты заменяются свежими уникальными данными.

После прохода slow + 1 — это количество уникальных значений, собранных в начале массива.

Всё, что находится после уникального начала массива, — оставшийся ненужный фрагмент. Задачу интересуют только первые slow + 1 элементов, поэтому оставьте хвост без изменений.

Пустой массив содержит ноль уникальных значений. Перед началом проверьте условие n == 0, чтобы не выйти за конец массива.

Этот шаблон с медленным и быстрым указателями работает за O(n) времени и использует O(1) дополнительной памяти — именно это требуется при жёстких ограничениях по памяти.

Вы удаляете дубликаты на месте в отсортированном массиве с помощью медленного и быстрого указателей.

В отсортированном массиве пара из медленного и быстрого указателей удаляет дубликаты за один проход O(n) без дополнительной памяти, возвращая slow + 1 как количество уникальных значений. 🎉