Этот алгоритм подходит для любых данных. С его помощью можно искать не только повторяющиеся числа, но и буквы, строки и другие хешируемые типы данных.

Почему простой подход неэффективен?

Казалось бы, найти дубликаты просто: можно взять список и для каждого элемента проверить его наличие в оставшейся части. Однако такой подход требует двух вложенных циклов, что даёт квадратичную сложность O(n²) — это очень неэффективно для больших данных.

Оптимальное решение через множества

В Python есть тип данных, который автоматически удаляет дубликаты — множества (set). Используя их, можно реализовать поиск дубликатов с линейной сложностью O(n).

Пример кода:

def find_duplicates(lst):
    seen = set()
    duplicates = []
    for item in lst:
        if item in seen:  # Проверка за O(1) благодаря множеству
            duplicates.append(item)
        else:
            seen.add(item)  # Добавление за O(1)
    return duplicates

Как это работает?

  1. Создаём пустое множество seen для отслеживания уникальных элементов.

  2. Проходим по списку один раз.

  3. Если элемент уже есть в seen, добавляем его в список дубликатов.

  4. Иначе — добавляем элемент в seen.

Сложность алгоритма:

  • Время: O(n) — один проход по списку + O(1) для операций с множеством.

  • Память: O(n) — в худшем случае (если все элементы уникальны) множество хранит все элементы.