Посчитать, сколько id пользователей есть в обоих списках, за линейное время
list_a и list_b содержат id пользователей. Верните, сколько различных пользователей есть в обоих списках. В каждом списке возможны дубли, но пользователь считается один раз.
Цельтесь в O(n + m) по времени — вложенный цикл, сканирующий list_b для каждого id из list_a, даст O(n * m) и будет слишком медленным на миллионах id.
def count_common_users(list_a: list[int], list_b: list[int]) -> int:
# ваш код здесьНапишите реализацию.
Превратите один список в set и посчитайте различные id другого в нём — членство в set это O(1), поэтому задача O(n + m). len(set(list_a) & set(list_b)) делает это одной строкой. Ловушка — if x in list_b, пересканирующий список.
- ✗Использовать
if x in list_bв цикле, получая O(n*m) - ✗Забывать убрать дубли id внутри каждого списка
- ✗Сортировать, когда пересечение set проще и быстрее
- →Почему перевод в set меняет класс сложности?
- →Как заодно вернуть сами id, а не только счёт?
Convert both lists to sets and intersect them — Python does the whole thing in O(n + m), and the sets remove within-list duplicates for free.
def count_common_users(list_a, list_b):
return len(set(list_a) & set(list_b))For list_a = [1, 1, 2, 3] and list_b = [3, 3, 4, 2] the sets are {1, 2, 3} and {2, 3, 4}; their intersection {2, 3} has length 2. The if x in list_b version would rescan list_b for every id in list_a, turning an O(n) job into O(n * m).
