Удаление дубликатов на месте
Используйте пару медленного и быстрого указателей
«Удаление дубликатов на месте» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Удаление дубликатов на месте
Дан отсортированный массив. Оставьте по одной копии каждого значения, не используя дополнительный массив. Обработка на месте экономит память и является классической задачей на собеседованиях. 🧹
Почему сортировка помогает
Когда массив отсортирован, каждый дубликат находится сразу рядом со своей копией. Поэтому достаточно сравнивать соседние элементы, а не весь массив.
Две роли, два указателя
Используйте медленный указатель, который отмечает последнее сохранённое значение, и быстрый указатель, который просматривает элементы дальше в поисках нового значения.
slow = 0
fast = 1Медленный указатель записывает
Представляйте медленный указатель как позицию записи: всё, что находится на нём или перед ним, уже очищено от дубликатов и содержит уникальные значения.
Быстрый указатель читает
Быстрый указатель лишь движется вперёд и читает элементы. Он забегает вперёд и сообщает медленному указателю только тогда, когда находит ещё не сохранённое значение.
Пропускайте повторы
Если a[fast] равно a[slow], это повтор, поэтому ничего не делайте, кроме продвижения fast. Дубликат будет незаметно пропущен.
for fast in range(1, n):
if a[fast] == a[slow]:
continueНайдено новое значение
Когда a[fast] отличается, сдвиньте медленный указатель вперёд и скопируйте туда новое значение. Так старые дубликаты заменяются свежими уникальными данными.
else:
slow += 1
a[slow] = a[fast]Ответ — это длина
После прохода slow + 1 — это количество уникальных значений, собранных в начале массива.
return slow + 1Не обращайте внимания на хвост
Всё, что находится после уникального начала массива, — оставшийся ненужный фрагмент. Задачу интересуют только первые slow + 1 элементов, поэтому оставьте хвост без изменений.
Помните о пустом массиве
Пустой массив содержит ноль уникальных значений. Перед началом проверьте условие n == 0, чтобы не выйти за конец массива.
if n == 0:
return 0Один проход, без дополнительной памяти
Этот шаблон с медленным и быстрым указателями работает за O(n) времени и использует O(1) дополнительной памяти — именно это требуется при жёстких ограничениях по памяти.
Быстрая проверка
Вы удаляете дубликаты на месте в отсортированном массиве с помощью медленного и быстрого указателей.
Повторение
В отсортированном массиве пара из медленного и быстрого указателей удаляет дубликаты за один проход O(n) без дополнительной памяти, возвращая slow + 1 как количество уникальных значений. 🎉
Часто задаваемые вопросы
Урок «Удаление дубликатов на месте» бесплатный?
Да — полный текст урока «Удаление дубликатов на месте» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Удаление дубликатов на месте»?
Используйте пару медленного и быстрого указателей Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Удаление дубликатов на месте»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Два указателя в отсортированном массиве
- Поиск пары с заданной суммой
- Удаление дубликатов на месте
- Слияние двух отсортированных последовательностей