Поиск дубликатов в массиве: от O(n²) к O(n)

Как эффективно найти дубликаты в массиве на Python

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

Наивный подход: список как контейнер

Когда я впервые столкнулся с задачей Contains Duplicate на LeetCode, моя первая мысль была: «Сохраняю каждый элемент в список и проверяю, не встречался ли он раньше». Вот код:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        container = []
        for elem in nums:
            if elem in container:
                return True
            container.append(elem)
        return False

Казалось бы, логично: мы жертвуем памятью ради скорости. Но на самом деле мы проигрываем по обоим параметрам. Почему? Всё дело в операции if elem in container.

Скрытая стоимость проверки вхождения в список

Когда вы проверяете elem in container для списка, Python вынужден перебирать элементы списка один за другим, пока не найдёт совпадение. В худшем случае (если элемента нет) он пройдёт по всем элементам. Для списка из 5 элементов — 5 проверок, для 100 — 100, для миллиарда — миллиард. И это на каждом шаге цикла! Получается, что общая сложность равна O(n²), а не O(n), как я ошибочно предполагал.

Решение с множеством (set): истинный O(n)

Множества в Python реализованы на основе хеш-таблиц, поэтому проверка вхождения элемента выполняется в среднем за O(1). Заменим список на множество:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        container = set()
        for elem in nums:
            if elem in container:
                return True
            container.add(elem)
        return False

Это решение уже работает за O(n) по времени, потому что каждая проверка и добавление занимают константное время. Мы по-прежнему используем дополнительную память O(n), но это оправдано.

Однострочное решение: сила множества

Но можно сделать ещё проще. Множество автоматически удаляет дубликаты. Если длина множества отличается от длины исходного массива, значит, дубликаты были:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

Этот вариант лаконичен и эффективен: построение множества занимает O(n), а сравнение длин — O(1). Итоговая сложность — O(n).

Почему множество лучше списка?

Список хранит элементы в порядке добавления, и поиск элемента требует линейного прохода. Множество использует хеширование, что даёт мгновенный доступ. Поэтому выбор структуры данных критически важен для производительности алгоритма.

Практический вывод

Прямо сейчас откройте свой редактор и решите задачу Contains Duplicate на LeetCode тремя способами: через список, через множество и через однострочник. Замерьте время на массиве из 10⁶ элементов — разница будет впечатляющей. Запомните: если нужно проверять наличие элемента, всегда используйте множество, а не список.