Find the Duplicate Number

Повторяющееся значение находится как минимум в двух позициях i < j. Сравни каждую позицию со всеми позициями после неё; первая пара с равными значениями и даёт ответ. В первом примере в позиции 1 находится 5, а при просмотре позиций начиная с 2 обнаруживается ещё одна 5 в позиции 4.

Так соблюдаются оба правила: ничего не записывается, а единственная используемая память — два счётчика циклов. Это медленно, потому что приходится сравнивать пары. При n+1 = 10,001 значениях, если оба экземпляра находятся ближе к концу, проверяется около 5 × 10^7 пар.

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

Если повторяющееся значение d больше m, значения от 1 до m встречаются не более одного раза каждое, поэтому количество не превышает m. Если d не превышает m, каждое значение больше m встречается не более одного раза, поэтому выше m находится не более n-m элементов, а не менее m+1 элементов не превышают m. Поэтому проверка «count > m» ложна для каждого m меньше d и истинна начиная с d. Бинарный поиск находит первое m, для которого она становится истинной, и это d.

Во втором примере n равно 4. При m = 2 элементы 2 и 1 дают количество 2, то есть не больше 2, поэтому ответ больше 2. При m = 3 количество по-прежнему равно 2, поэтому ответ — 4. На каждом шаге весь массив просматривается один раз, а диапазон делится пополам, поэтому объём работы составляет O(n log n): около 14 проходов по 10,001 значениям.

Рассматривайте массив как набор ссылок: позиция i указывает на позицию nums[i]. У каждой позиции от 0 до n есть ровно одна исходящая ссылка, и каждая ссылка ведёт куда-то от 1 до n. В первом примере ссылки такие: 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 и 5 → 4.

Начните с позиции 0 и следуйте по ссылкам. Путь не может оборваться, потому что у каждой позиции есть ссылка, а всего позиций n+1, поэтому рано или поздно вы вернётесь к уже посещённой позиции. После этого путь будет бесконечно ходить по кругу. Путь состоит из хвоста и цикла, напоминая букву ρ. В первом примере путь такой: 0, 2, 1, 5, 4, 5, 4 и так далее: хвост — 0, 2, 1, а цикл — 5, 4. Позиция 3 указывает сама на себя, но путь до неё никогда не доходит, и это не мешает.

Вход в цикл — это дубликат. Путь дважды входит в позицию 5 из разных мест: один раз с конца хвоста (позиции 1, потому что nums[1] равно 5) и один раз с конца цикла (позиции 4, потому что nums[4] равно 5). В двух разных позициях хранится значение 5, поэтому 5 повторяется. Хвост всегда содержит позицию 0, потому что ни одно значение не равно 0 и ни одна ссылка никогда не ведёт обратно к ней, поэтому у входа всегда есть эти два разных пути. Повторяется ровно одно значение, значит, вход соответствует этому значению.

Теперь найдите вход с помощью двух указателей, как при обнаружении цикла в связном списке. На первом этапе slow проходит по одной ссылке за раунд, а fast — по двум, пока они не окажутся в одной позиции где-то в цикле. В первом примере они встречаются в позиции 4. На втором этапе верните slow в позицию 0, оставьте fast на месте и передвигайте оба указателя на одну ссылку за раунд. Они встретятся на входе в цикл.

Почему работает второй этап: пусть хвост состоит из T ссылок до входа в цикл, а в цикле C позиций. Когда указатели встретились, slow прошёл s шагов, а fast — 2s. Они стояли в одной точке, значит, дополнительные s шагов fast составили целое число кругов цикла. Ещё через T шагов slow достигнет входа в цикл из позиции 0, а fast окажется там же, где был бы путь из позиции 0 через s+T шагов, поскольку дополнительные круги ничего не меняют. Это T шагов до входа плюс s шагов — целое число кругов, — поэтому fast тоже окажется на входе. Раньше они встретиться не могут, потому что slow всё ещё находится в хвосте, а fast не выходит из цикла. В первом примере slow проходит позиции 2, 1, 5, а fast — 5, 4, 5, и они встречаются в позиции 5 через T = 3 шага.

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