12.01.2026 07:00
demitryy 34 9400 Источник

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

Наступил 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) доп. памяти.

Ссылки

Комментарии (34)


  1. CrazyElf
    12.01.2026 08:08
    #29370848

    Плохо только то, что максимальное число попыток теоретически не ограничено. В очень редком случае рандом может выпадать так, что цикл будет продолжаться бесконечно. )
    Так что интересно было бы увидеть решение O(1) без рандома. Рандом, кстати, несколько затратный по ресурсам. Это, конечно, константа, но...
    Кстати, из тех же самых соображений о минимальном числе попыток, ваш самый первый метод с хэшем по идее превращается в такой же константный и интуитивно думаю, что даже с меньшим числом попыток, ведь мы сравниваем очередное число не с одним, а со всеми числами, которые на данный момент есть в словаре.


    1. demitryy Автор
      12.01.2026 08:08
      #29370978

      Если массив был случайно перемешан, да. Однако, если нам назло подсунули плохой массив, будет O(n), например:

      [1, 2, 3, ..., 1000, 1, 1, 1, ..., 1]

      Решение за O(1) по памяти без рандома здесь: https://youtu.be/B-1h5xEjBvk?si=RVxUnYKOJnnx-wZK&t=791


      1. CrazyElf
        12.01.2026 08:08
        #29371096

        Видео не хотелось бы смотреть ) Почему бы в тексте это решение не показать? ) Но, повторюсь, по факту решение с set и есть O(1), если не брать совсем уж злонамеренные данные.


      1. nik_the_spirit
        12.01.2026 08:08
        #29371290

        Авторы видео ошиблись решение не за O(1), а за O(n), так как в итоге они итерируются по всей длине массива. А так как это вложенный цикл, то они в итоге это делают 3 раза.


        1. demitryy Автор
          12.01.2026 08:08
          #29371848

          O(1) по памяти, а не по времени.


  1. CrazyElf
    12.01.2026 08:08
    #29370984

    В итоге я погонял тесты. Интуиция меня всё-таки обманула:

    • метод с random и метод с set практически одинаковые по скорости работы

    • среднее число попыток у них одинаковое: 4

    • при этом у random больше разброс количества попыток и (что логично из этого вытекает) почти в 2 раза больше максимальное число попыток, которое понадобилось

    Таким образом, вполне можно считать, что метод с set тоже O(1) и по скорости и по памяти, и при этом он стабильнее, чем метод с random (меньше разброс требуемых попыток, а значит и времени работы метода).

    P.S. Конечно, если подавать злонамеренно подготовленные данные, то метод с random предпочтительнее. Метод с set, если ему злонамеренно ставить в конец повторяющееся число, будет всегда перебирать половину массива. Конечно, можно перебирать тогда специально в обратном порядке, но тогда можно ставить эти числа в середину, и перебираться всё-равно будет четверть массива, хоть по порядку перебирай, хоть обратно. Но если злонамеренность не ожидается, то метод с set предпочтительнее.


    1. demitryy Автор
      12.01.2026 08:08
      #29371010

      Если массив на вход подается случайный, то метод random ничего нового не привносит. Разумеется, он только замедлит. Однако, на плохих входах будет деградация до O(N).


    1. D_T
      12.01.2026 08:08
      #29371374

      Можно совместить set и random. Обход массива сделать со случайного выбранного элемента и случайно выбранным шагом:

      step = random() % 2n;

      i = random() % 2n;

      for(j = 0; j < 2n; j++) {

      i = (i + step) % 2n;

      ... проверка array[i]

      }


      1. CrazyElf
        12.01.2026 08:08
        #29371420

        Да, у меня тоже была такая мысль - в начале random, а потом уже set )


    1. CrazyElf
      12.01.2026 08:08
      #29371442

      Тьфу, блин, я неправильно считал. Я считал число итераций цикла. И в случае с set будет 4 шага по циклу, но на первом то шаге мы ничего не сравниваем, сравнения начинаются со второго шага. Значит, интуиция меня всё-таки не обманула - в варианте с set достаточно в среднем 3-х проверок, как я и предполагал. ) Что меньше, чем 4 для random варианта.
      Кстати, для массивов маленького размера возможно list даже будет быстрее, чем set.


  1. D_T
    12.01.2026 08:08
    #29371140

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


    1. Deosis
      12.01.2026 08:08
      #29375872

      Если половина элементов одинаковые, то в худшем случае они расположены через один.

      Поэтому можно идти по массивы и сравнивать текущий элемент с предыдущим и предпредыдущим. Первое же совпадение и будет искомым элементом.


  1. axion-1
    12.01.2026 08:08
    #29371182

    Использовать рандом в таких задачах плохой тон, т.к. в общем случае алгоритм может зацикливаться, при этом есть простые алгоритмы гарантированно находящие решение за O(n).

    Например, если понадобится модифицировать условие так что число повторяется не n раз а 2, и количество элементов будет например 10 миллионов, алгоритм с рандомом перестанет работать за вменяемое время.


  1. Alexandroppolus
    12.01.2026 08:08
    #29372006

    Можно последовательно рассматривать тройки чисел: сначала попарно сравнивать первые 3 числа (arr[0], arr[1], arr[2]), потом (arr[3], arr[4], arr[5]), и т.д. Рано или поздно придем к такой тройке (или остаточной двойке чисел), где есть два одинаковых элемента

    Это не сработает, если длина массива меньше 6, но частный кейс не проблема. Зато вариант будет работать, даже если искомое число встречается не в половине элементов массива, а чуть более чем в трети.


    1. demitryy Автор
      12.01.2026 08:08
      #29372080

      Да, именно так :)

      Решение авторов именно такое.


      1. Alexandroppolus
        12.01.2026 08:08
        #29372106

        А, ну ок. Я отлучен от ютуба, государство позаботилось, уберегло...


    1. CrazyElf
      12.01.2026 08:08
      #29372660

      Толково. Добавил к моим тестам, по времени получается примерно как другие два метода, при этом в среднем тут достаточно двух шагов алгоритма, чтобы найти число.


      1. wataru
        12.01.2026 08:08
        #29373032

        В среднем - это на случайных массивах. Худший случай тут O(n) на плохом тесте.


        1. CrazyElf
          12.01.2026 08:08
          #29376036

          Ну, у многих алгоритмов худшая сложность отличается от типовой, это нормально.


    1. wataru
      12.01.2026 08:08
      #29373026

      Есть другой вариант: рассмотрите каждую из n/2 соседних пар. Если нашли совпадение - это ответ. если не нашли, то у нас эти n повторяющихся элементов разбиты по n парам, по одной в каждой. Значит среди, первых (или последних) четырех точно есть повторение. Так что надо сравнить arr[0] с arr[2] и arr[3]. Если совпало - вы нашли число arr[0]. Если нет, то искомое число arr[1].

      Тут нет частных случаев, работает даже для n=4. Для n=2 задача не имеет смысла, ибо "повторяющееся" число там повторяется один раз и никак не отличимо от уникального числа.


      1. demitryy Автор
        12.01.2026 08:08
        #29373402

        Шикарное решение, спасибо!


  1. wataru
    12.01.2026 08:08
    #29373502

    А вот интересный вопрос: как решать усложненную задачу, где одно число встречается ровно N/2 раз, а все остальные меньше и они могут повторятся? Отличие от изначальной задачи, что вспомогательные редкие числа уже не уникальны и нельзя любую пару совпадающих чисел считать ответом. Но все-равно только одно число самое частое и встречается N/2 раз.

    Тут ясно, как делать с сортировкой или hash-map-ами. Но за O(N) по времени и O(1) памяти это как сделать?

    Чуть более простую задачу, где ровно одно число встречается строго больше N/2 раз, известно, как решать - там надо "аннигилировать" различные элементы парочками. Поддерживаем инвариант, что у нас среди рассмотренных чисел уничтожены все, кроме скольких-то копий одного числа. При добавлении нового числа в рассмотрение оно или аннигилирует с существующим или добавляется к ответу. Последнее не уничтоженное число - это и будет ответ:

    int current = 0;
int cnt = 0;
for (int x : arr) {
  if (x == current) {
    ++cnt;
  } else {
    if (cnt == 0) {
       cnt = 1;
       current = x;
    } else {
       --cnt;
    }
  }
}
return current;

    Это работает, потому что даже если вы уничтожаете в каждой парочке искомое число, вы все его копии не уничтожите, ибо их больше N/2, а аннигиляций будет не больше N/2. Если же вы какие-то левые элементы вместе уничтожите, то тем более искомое число останется в конце.

    Но вот если у вас ровно N/2 самого частого числа, а всех остальных строго меньше, то это уже не сработает. Можно нечаянно уничтожить все копии искомого. Тут мне видится одно решение: если в конце осталось что-то, то это ответ. Если же в конце осталось 0 чисел, то мы во всех парочках аннигилировали искомое число с чем-то еще. Теоретически, можно просто отслеживать, какие числа мы аннигилировали и запоминать те одно-два, которые встречались во всех аннигилирующих парах. С каждой новой аннигиляцией вычеркнуть те, что не повторились. В конце должно остаться ровно одно число

    Есть ли у кого-нибудь идеи попроще?


    1. Alexandroppolus
      12.01.2026 08:08
      #29373878

      Аннигилировать тройки. Это обобщение упомянутого Бойера-Мура, я как-то уже писал

      Останутся 2 кандидата, далее проверка одного из них.

      Не уверен, что это проще, но зато работает и на меньшем количестве искомого числа.

      А если говорить про вашу идею с аннигиляцией пар, то в ситуации, когда осталось 0 чисел, у нас так же есть два кандидата - самая первая уничтоженная пара. Проверяем одно число из этой пары.


      1. wataru
        12.01.2026 08:08
        #29374030

        Проверяем одно число из этой пары.

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


      1. wataru
        12.01.2026 08:08
        #29374042

        Аннигилировать тройки

        А вот тут не понял, как это должно работать? Типа нашли 2 числа, каждое из которых встречается больше n/3 раз и потом их оба проверить на количество вхождений n/2?


        1. Alexandroppolus
          12.01.2026 08:08
          #29374066

          Проверить только одно из них. Если его не N/2 штук, то искомое - другое.


  1. lightln2
    12.01.2026 08:08
    #29375140

    Хорошая задача, она демонстрирует основной результат теории, которую называют красивым словом "heavy hitters theory" (не знаю, как правильно перевести на русский - может, "важные чуваки"?)
    Лет 10 назад она активно развивалась, и было много научных работ на эту тему (последнее время я за ней не слежу, может, до сих пор там что-то новое придумывают)
    Там два основных результата - это теорема Бойера-Мура о поиске значений, встречающихся в потоке больше половины раз , о которой @Alexandroppolus упоминает, и ее обобщение на n/k раз теорема Мисра-Грис.
    Также там активно исследовались вероятностные методы, так что идея автора (если я правильно понимаю) - очень хорошая на практике, потому что вероятность ложного результата обычно падает экспоненциально по количеству попыток. То есть, если взять ваш алгоритм и повторить раз 50, то вероятность его ошибки будет сильно меньше вероятности того, что прилетит заряженная частица с солнца и поменяет бит в памяти компьютера. Конечно, есть еще вероятность злонамеренной атаки на генератор случайных чисел, но эта проблема тоже имеет теоретическое решение :)
    Ну и важная часть исследований доказывает разные ограничения. Я знаю реальный случай, когда начальник попросил программиста найти моду (самое повторяющееся значение в потоке) с использованием констатной памяти. Программист ему гордо показал теорему, которая говорит, что это невозможно!


    1. demitryy Автор
      12.01.2026 08:08
      #29378314

      Спасибо за комментарий и ссылки на теоремы!


  1. vityo
    12.01.2026 08:08
    #29375156

    Фу, что за фигня. Мы точно решаем или неточно. Есть разница между четкими и приблизительными ответами. Как четкие и нечёткие множества. Короче зависит от тестовых данных. Рандом вообще не причем тут, они ведь уже перемешаны по условию, можно линейно читать считая что рандомно уже применил индекс.

    И если решать четко и без памяти особой. То я бы хранил хеш переменную с типом чисел, и xor на каждом шаге с ней текущего, и наверно проверяя с хешем на предыдущем шаге тоже через xor и что-то там смотреть на 0 или не 0 значит нашли. Будет n/2 в худшем итого o(n) как ни крути.

    А так, да, если нечеткость решения норм, то можно в зависимости от степени нечеткости Альфа от 0 до 1 выбрать такое k = f(a, n) и потом брать случайно k чисел и также их перебирать, будет просто степень ответа нечеткая.


    1. demitryy Автор
      12.01.2026 08:08
      #29378222

      Рандом вообще не причем тут, они ведь уже перемешаны по условию

      Где такое можно прочитать?)

      Наоборот, если мы говорим про олимпиадное программирование, где все тесты запускаются независимо, то опытные составители обязательно подсунут вам тесты, на которых без рандома все будет работать медленно.

      Мы точно решаем или неточно.

      Мне кажется, вы путаете два разных понятия: приближенные и рандомизированные алгоритмы. Первые - выдают ответ с определенной погрешностью. Вторые - просто используют внутри себя рандом (как например quick sort).


      1. vityo
        12.01.2026 08:08
        #29380608

        Вы называете решение “быстрее”, но оно быстрее только за счёт рандома.

        Алгоритм может крутиться сколько угодно долго — просто с маленькой вероятностью.

        Линейное решение без рандома всегда заканчивается и даёт тот же точный ответ.

        Поэтому вы сравниваете гарантированное решение с негарантированным, и из-за этого вывод про “O(1)” вводит в заблуждение.


  1. VOVKT
    12.01.2026 08:08
    #29376644

    Тоже решал это на литкоде. В целом, задача сводится к поиску пары, при распределении чисел у нас есть всего несколько вариантов:

    • Элемент повторяется один за другим [1,2,3,3]

    • Рядом стоят не повторяющиеся элементы

      • [1,3,2,3]

      • [3,1,2,3]

      • [3,1,3,2]

    С первым случаем все понятно, сравниваем пары чисел и если одинаковые - выходим. Дальше идут два случая, когда повторяющийся элемент последний. И последний случай - это когда наш искомый элемент предпоследний.

    def repeatedNTimes(nums: List[int]) -> int:
    prev = last = nums.pop()
    for cur in nums:
        if cur == prev or cur == last:
            return cur
        else:
            prev = cur
    return prev

    Здесь cur == prev это проверка на повторяющиеся подряд, cur == last проверяем, что повторяющийся элемент последний и return prev как наш последний вариант, когда повторяющийся элемент предпоследний.

    Можно было тоже самое считать с первыми элементами, но с последними мне показалось проще.


  1. aamonster
    12.01.2026 08:08
    #29379968

    В таких задачах обычно оптимизируют наихудшее время, иногда амортизированное. Если б вы сразу сказали про среднее – задачка была бы тривиальной...


  1. Katasonov
    12.01.2026 08:08
    #29380170

    Возможно я не так понял что имеется ввиду под искомой парой или "со второго раза", но поясните пожалуйста откуда взялась вероятность того что мы найдем искомую пару со второго раза с вероятностью (3/4)×(1/4) ? Если под "раз" тут имеется ввиду попытка найти пару например 5,5 из примера, то разве вероятность второй раз найти искомую пару не равна так же 1/4? За счёт чего эта вероятность увеличивается?