Привет, Хабр!

Наступил 2026-й год, и, по своей традиции, в январские праздники я снова занялся решением задач на LeetCode уже четвертый год подряд. Каждый день я открываю задачу дня и решаю ее.

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

Условие

Дан массив целых чисел nums длины 2n (n >=2). В массиве есть n + 1 различных чисел. При чем n чисел встречаются по одному разу, и 1 число повторяется ровно n раз.

Нужно найти и вернуть число, которое повторяется n раз.

Примеры

  • [1, 2, 3, 3] -> 3

  • [2, 1, 2, 5, 3, 2] -> 2

  • [5, 1, 5, 2, 5, 3, 5, 4] -> 5

Решение (в лоб)

Самое первое, что может прийти в голову - завести множество (в плюсах std::unordered_set или set в питоне).

Ниже приведен код на Python.

def repeatedNTimes(nums: List[int]) -> int:
    num_set = set()
    for num in nums:
        if num in num_set:
            return num
        num_set.add(num)

Time complexity: O(n)
Space complexity: O(n)

Можно лучше?

Как можно было догадаться из заголовка - да!

И так, мы хотим полностью избежать потребления доп. памяти, т.е. не выделять дополнительных set-ов. И вот идея:

Просто посмотрим на массив из примера: [5, 1, 5, 2, 5, 3, 5, 4]. Куда в нем ни ткни, мы с хорошей вероятностью (а именно с вероятностью p=\frac{4}{8}=\frac{1}{2}) попадем в 5 (искомый элемент). Так происходит всегда, потому что по условию размер массива 2n, а искомый элемент содержится в нем ровно n раз, т.е. p=\frac{n}{2n}=\frac{1}{2}.

Тогда давайте просто ткнем в любые 2 случайных элемента. Вероятность, что это будут два искомых элемента составляет p^2 = \frac{1}{4}. Это значит, что в среднем каждый четвертый раз мы будем угадывать подходящую пару элементов и как только мы угадали, мы сразу это поймем, т.к. элементы в ней совпадут.

Более формально

Вероятность, что мы найдем подходящую пару с первого раза: p_1=\frac{1}{4}

Вероятность, что мы найдем подходящую пару со второго раза: p_2=\frac{3}{4}\cdot \frac{1}{4}

Вероятность, что мы найдем подходящую пару с третьего раза: p_2=\frac{3}{4}\cdot \frac{3}{4} \cdot \frac{1}{4}

Вероятность, что мы найдем подходящую пару с {k }-го раза: p_k=\Big(\frac{3}{4}\Big)^{k-1} \cdot\frac{1}{4}

Введем случайную величину "число попыток до угадывания". Тогда мат. ожидание данной случайной величины равно

\mathbb{E} = \sum_{k=1}^{\infty} k \cdot p_k = \sum_{k=1}^{\infty} k \cdot \Big(\frac{3}{4}\Big)^{k-1} \cdot \frac{1}{4} =\frac{1}{4} \cdot \frac{4}{3} \cdot \sum_{k=1}^{\infty} k \cdot \Big(\frac{3}{4}\Big)^{k}

Теперь раскроем сумму ряда:

\sum_{k=1}^{\infty} k \cdot \Big(\frac{3}{4}\Big)^{k} = \frac{\frac{3}{4}}{\left(1-\frac{3}{4}\right)^2} = \frac{\frac{3}{4}}{\left(\frac{1}{4}\right)^2} = \frac{3}{4} \cdot 16 = 12

Подставляем обратно:

\mathbb{E}=\frac{1}{3} \cdot 12 = 4

Таким образом, в среднем подходящая пара будет найдена с четвёртой попытки.

Код:

def repeatedNTimes(nums: List[int]) -> int:
    n = len(nums)
    while True:
        i = randint(0, n - 1)
        j = randint(0, n - 1)
        if i != j and nums[i] == nums[j]:
            return nums[i]

Time complexity: O(1) в среднем
Space complexity: O(1)

Заключение

Спасибо, что дочитали до конца. На ютубе также есть видео с авторским решением без использования случайных чисел за O(1) доп. памяти.

Ссылки