Условие
Дима — начинающий программист. Он совсем недавно устроился в новую компанию и теперь пишет программу для анализа данных.
Однажды Дима пришел на работу и заметил, что в программе начали появляться дубликаты данных. Беда! Повторяющиеся элементы могут исказить результаты анализа, ведь некоторые характеристики учитываются дважды, а это влияет на точность выводов.
Задача
Помогите Диме доработать код. Напишите функцию, которая принимает на вход несортированный связный список и удаляет из него все дубликаты.
Решение
Задачу можно решить несколькими способами. Покажем два варианта и разберем, в каких случаях они уместны.
Движение по списку с использованием двух указателей
def remove_duplicates(first):
if not first:
return
nextone = first
while nextone:
runner = nextone
while runner.next:
if runner.next.val == nextone.val:
runner.next = runner.next.next
else:
runner = runner.next
nextone = nextone.next
return first
Что делает код
Функция remove_duplicates принимает на вход один аргумент first, в который мы передаем начало списка.
Далее создаем переменную nextone, которая инициализируется значением first. Nextone используем для перемещения по списку, она указывает на текущий элемент. То есть эта переменная является первым указателем. Переменная runner — второй указатель. Она понадобится нам для удаления дубликатов.
Первый указатель, nextone, перемещается по списку один раз. Затем для каждого элемента списка мы проверяем наличие дубликатов при помощи вложенного цикла и, если какие-то элементы повторяются, удаляем их. В результате получаем список без дубликатов.
Этот подход позволяет удалить повторы, не используя при этом дополнительную память для хранения значений или указателей.
Сложность
Time: O(n^2)
Space: O(1)
Плюс: решение не требует дополнительного выделения памяти.
Минус: временная сложность решения — O(n^2), так как для каждого элемента придется пройти весь оставшийся список.
Этот вариант можно использовать для небольших списков, но для крупных лучше выбрать другое решение.
Метод с использованием хеш-таблицы
Этот подход к удалению дубликатов в связанном списке использует хеш-таблицу, чтобы отслеживать пройденные уникальные значения.
def remove_duplicates(list_head):
if not list_head:
return
seen = set()
current = list_head
prev = None
while current:
if current.val in seen:
prev.next = current.next
else:
seen.add(current.val)
prev = current
current = current.next
return list_head
Что делает код
Функция remove_duplicates принимает на вход один аргумент list_head, в который мы передаем начало списка. Сначала она проверяет, пуст ли список (not list_head). Если да, она возвращает результат и завершает работу. Если в списке содержится хотя бы один элемент, функция начинает их обрабатывать.
Далее создаем множество seen, которое будем использовать для отслеживания уникальных значений связанного списка.
Задаем две переменные: current и prev. Переменную current помещаем в начало списка, а prev станем использовать для отслеживания предыдущего элемента. То есть мы будем проходить по элементам, начиная с головы списка, и проверять, встречались ли нам уже какие-либо значения.
Далее запускаем цикл while — он выполняется до тех пор, пока current не достигнет конца списка. Внутри цикла проверяем, содержится ли значение текущего элемента current.val во множестве seen. Если значение уже есть, переустанавливаем указатель prev на следующее. Если значение отсутствует во множестве, добавляем его в seen и переносим указатель prev на текущий элемент. После обработки текущего элемента списка переходим к следующему, обновляя переменную current.
Сложность
Time: O(n)
Space: O(n)
Плюс: улучшенная эффективность по времени.
Минус: выделяется дополнительная память.
Итоги
В первом решении эффективное использование памяти, но из-за этого значительно ухудшилась эффективность по времени. Решение O(n^2) считается довольно медленным, это особенно заметно на больших объемах данных.
Во втором варианте мы дополнительно выделяем память под Set, сохраняя встречающиеся значения. Проверка дублей в Set имеет константную сложность по времени, из-за чего время проверки на дубли остается линейным.
