Дан массив nums из n + 1 целых чисел, где каждое число находится в диапазоне от 1 до n включительно. В массиве есть только одно повторяющееся число, найдите его и верните.
Необходимо решить задачу, не изменяя массив nums и используя только константное дополнительное пространство.
Пример 1:
Входные данные: nums = [1,3,4,2,2]
Выходные данные: 2
Пример 2:
Входные данные: nums = [3,1,3,4,2]
Выходные данные: 3
Алгоритм "Черепаха и заяц" позволяет найти повторяющийся элемент в массиве без модификации самого массива и используя только константное дополнительное пространство. Алгоритм заключается в том, что мы используем два указателя - медленный и быстрый. Медленный указатель двигается на один элемент за раз, а быстрый указатель двигается на два элемента за раз. Если в массиве есть повторяющийся элемент, то рано или поздно быстрый указатель догонит медленный указатель.
Когда быстрый указатель догоняет медленный, мы находимся в цикле. Так как в массиве есть только один повторяющийся элемент, то найденная точка схода указателей является повторяющимся элементом.
Рассмотрим массив nums = [1,3,4,2,2]
Медленный указатель и быстрый указатель начинают с индекса 0:
| Шаг | Медленный указатель | Быстрый указатель |
|---|---|---|
| 0 | 1 | 3 |
| 1 | 3 | 2 |
| 2 | 4 | 4 |
| 3 | 2 | 2 |
Быстрый указатель догнал медленный указатель на 3-ем шаге, находим точку схода указателей - элемент с индексом 2. Этот элемент является повторяющимся элементом.