Мини-урок · перед практикой
Количество совпадающих пар
Каждый новый элемент образует пары со всеми прежними равными.
Как к ней подойти
Потренируйтесь хранить последовательность значений и обращаться к нужным элементам списка.
Коротко о теме
Список хранит элементы в определённом порядке. Прежде чем менять его, решите, нужны ли исходные индексы и можно ли пройти по данным один раз. При удалении элементов будьте внимательны: индексы сдвигаются.
Ключевая идея · Частоты на ходу
Пара учитывается ровно при обработке её правого элемента.
Проверьте перед запуском
- Для k одинаковых чисел получается k(k−1)/2 пар.
После практики
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Частоты на ходу
Пара учитывается ровно при обработке её правого элемента.
a = list(map(int, input().split()))
counts = {}
answer = 0
for x in a:
answer += counts.get(x, 0)
counts[x] = counts.get(x, 0) + 1
print(answer)
Время: O(n) в среднем. Память: O(n).
Другой способ: Все пары индексов
Перебор j<i исключает повторный подсчёт и пары элемента с самим собой.
a = list(map(int, input().split()))
answer = 0
for i in range(len(a)):
for j in range(i):
if a[i] == a[j]:
answer += 1
print(answer)
Время: O(n²). Память: O(n).