MiddleКодИногдаЕщё не отвечали
Удалить дубликаты из списка, сохранив порядок
Дан список с повторами; верните новый список без дубликатов, сохранив порядок первого появления.
Требования:
- сохранить порядок первого появления
- O(n) время
def dedup(items: list) -> list:
# ваш код здесь
# dedup([1, 1, 1, 2, 2, 3, 3, 3, 4]) -> [1, 2, 3, 4]Допишите реализацию.
Самый чистый способ с сохранением порядка — list(dict.fromkeys(items)): ключи словаря уникальны и с 3.7 хранят порядок вставки. Эквивалентно: пройти один раз и добавлять элементы, которых ещё нет в множестве seen, что даёт O(n). Простой set(items) убирает дубликаты, но теряет порядок, поэтому не удовлетворяет требованию.
- ✗Использовать
set(items), считая, что порядок сохранится - ✗Просматривать результирующий список на каждый элемент, делая O(n^2)
- ✗Сортировать сначала и утверждать, что исходный порядок сохранён
- →Почему
dict.fromkeysсохраняет порядок, аsetнет? - →Как убрать дубликаты из списка нехешируемых элементов, например словарей?
