Find the Duplicate Number

Средняя№287цикл

Дан массив из n + 1 чисел, каждое от 1 до n, поэтому какое-то число обязательно повторяется; повторяется ровно одно значение, возможно, больше двух раз. Найди его, не меняя массив и с O(1) дополнительной памяти. Наш пример: [3, 5, 4, 6, 1, 2, 1], n = 6 — ответ 1.

287 Find the Duplicate NumberРазбор · 1×

Пример: [3, 5, 4, 6, 1, 2, 1]: индекс i ведёт к индексу nums[i]. Внизу — индексы в том порядке, в каком по ссылкам приходишь к ним от 0.

031524364152610361524slow
slowfastповтор и две его ячейки

Ни в одной ячейке нет 0, поэтому в индекс 0 не ведёт ни одна ссылка: это голова списка. slow = nums[0] = 3

01/24
сначала · назад · пуск · шаг
Скорость
1function findDuplicate(nums):
2 slow = nums[0]
3 fast = nums[nums[0]]
4 while slow != fast:
5 slow = nums[slow]
6 fast = nums[nums[fast]]
7 slow = 0
8 while slow != fast:
9 slow = nums[slow]
10 fast = nums[fast]
11 return slow
состояние
slow
3
fast
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Все значения от 1 до n, поэтому каждая ссылка ведёт на настоящий индекс и ни одна — на 0: от 0 по ссылкам можно идти бесконечно, а индексов всего n + 1, значит, путь уходит в петлю.
  2. Петля начинается в индексе, в который ведут две ссылки: одна с хвоста, другая с конца петли. Этот индекс записан в двух ячейках, значит, он и есть повтор.
  3. Найти начало петли — это Linked List Cycle II: встретиться внутри, вернуть slow в начало и вести обоих по одному шагу. Массив только читаем, а вся память — два индекса.

Сложность

Время O(n): каждый цикл делает не больше примерно n шагов, как в Linked List Cycle II. Память O(1): два индекса, массив не меняется.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.