Как найти повторяющиеся числа: множество или сортировка

Условие

Дан массив целых чисел. Нужно определить, встречается ли какое-либо значение более одного раза. Сравните решение через множество и решение через сортировку; исходный массив менять нельзя.

Ответ

Множество позволяет найти повтор за ожидаемое O(n) время и O(n) памяти. Сортировка копии занимает O(n log n), после чего достаточно сравнить соседние элементы.

Решение с множеством запоминает уже встреченные значения и заканчивает обход при первом повторе:

def has_duplicate(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

assert has_duplicate([3, 1, 3]) is True
assert has_duplicate([3, 1, 2]) is False
assert has_duplicate([]) is False

Альтернатива: ordered = sorted(values), затем проверить равенство каждой пары соседей. Копия сохраняет входной массив, но тоже требует O(n) памяти. Сортировку удобно выбирать, если упорядоченные данные нужны и на следующих шагах; для одной проверки повторов обычно проще множество.