JuniorКодИногдаЕщё не отвечали
Отфильтровать виденные id, сохранив исходный порядок
Даны recom_ids и seen_ids. Верните новый список в том же порядке, что recom_ids, но без любого id, встречающегося в seen_ids.
Требования:
- Сохраните порядок
recom_ids. - Цель — O(n) суммарно, а не вложенный перебор за O(n*m).
def filter_seen(recom_ids, seen_ids):
# ваш код здесьДопишите реализацию.
Преобразуйте seen_ids в set один раз, затем пройдите recom_ids, оставляя элементы, чей id not in этого множества. Множество даёт O(1) проверку принадлежности, поэтому весь проход O(n); проверка in по списку сделала бы каждый тест O(m), а итог O(n*m). Проход по recom_ids напрямую сохраняет порядок.
- ✗Оставлять
seen_idsсписком, так что каждая проверкаinO(m), а итог O(n*m) - ✗Использовать разность множеств, теряя нужный порядок
recom_ids - ✗Менять
recom_idsна месте во время итерации вместо построения нового списка
- →Почему преобразование
seen_idsв множество меняет общую сложность? - →Как сохранить порядок, если всё же использовать разность множеств?
Оглавление
Задача
Реализуйте filter_seen: верните элементы recom_ids в исходном порядке, исключив встречающиеся в seen_ids, за O(n).
Решение
def filter_seen(recom_ids, seen_ids):
seen = set(seen_ids) # O(1) проверка принадлежности
return [x for x in recom_ids if x not in seen]Ключевые моменты
set(seen_ids)строится один раз за O(m); далее каждая проверкаnot in— O(1).- Проход по
recom_idsнапрямую сохраняет порядок — разность множеств этого не гарантирует. - Без множества проверка
inпо списку сделала бы алгоритм O(n*m).
Оглавление
