Мини-урок · перед практикой
Количество совпадающих чисел
Пересечение множеств оставляет общие различные числа.
Как к ней подойти
Увидите, как множества помогают сравнивать группы без повторяющихся элементов.
Коротко о теме
Множество хранит каждый элемент один раз. Пересечение a & b оставляет общие элементы, разность a - b - только элементы a, а объединение a | b собирает обе группы. Если важен порядок вывода, отсортируйте результат отдельно.
Ключевая идея · Пересечение
Повторы внутри списков не влияют на число общих значений.
Проверьте перед запуском
- Считаются различные общие значения, а не пары вхождений.
После практики
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Пересечение
Повторы внутри списков не влияют на число общих значений.
a = set(map(int, input().split()))
b = set(map(int, input().split()))
print(len(a & b))
Время: O(n+m) в среднем. Память: O(n+m).
Другой способ: Два указателя
В отсортированных списках сдвигаем указатель у меньшего значения, а при совпадении оба.
a = sorted(set(map(int, input().split())))
b = sorted(set(map(int, input().split())))
i = j = count = 0
while i < len(a) and j < len(b):
if a[i] == b[j]:
count += 1
i += 1
j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
print(count)
Время: O(n log n + m log m). Память: O(n+m).