Rotate Array

Средняя№189навстречу

Дан массив чисел и число k. Нужно сдвинуть массив по кругу на k позиций вправо: числа, которые выпадают с конца, возвращаются в начало. Делать это нужно в том же массиве, без второго. Наш пример: [1, 2, 3, 4, 5, 6], k = 2 → [5, 6, 1, 2, 3, 4].

189 Rotate ArrayРазбор · 1×

Пример: [1, 2, 3, 4, 5, 6], k = 2. Три разворота: весь массив, потом первые k, потом остальные. В каждом left и right идут навстречу с концов своего отрезка и меняют числа местами.

Сдвиг вправо на k = 2011223344556
в этом развороте, ещё не менялисьпод указателемтолько что поменялисьуже поменялисьвне этого разворота

n = 6: в массиве 6 чисел

01/30
сначала · назад · пуск · шаг
Скорость
1function rotate(nums, k):
2 n = len(nums)
3 k = k mod n
4 reverse(nums, 0, n - 1)
5 reverse(nums, 0, k - 1)
6 reverse(nums, k, n - 1)
7 return nums
8
9function reverse(nums, left, right):
10 while left < right:
11 swap nums[left] and nums[right]
12 left = left + 1; right = right - 1
состояние
n
6
k
–
left
–
right
–
nums
[1, 2, 3, 4, 5, 6]
нажмите шаг, чтобы вернуться

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

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

  1. После сдвига последние k чисел стоят в начале, а остальные — за ними. Разворот всего массива уже ставит каждую группу на своё место, только каждая группа оказывается задом наперёд.
  2. Разворот каждой группы по отдельности переворачивает её обратно, и порядок внутри группы становится прежним.
  3. Сдвиг на n возвращает массив на место, поэтому k, равное n или больше, сдвигает так же, как k mod n. Сначала берём k = k mod n, иначе разворот первых k выйдет за конец массива.

Сложность

Время O(n): за три разворота каждое число меняется местами не больше двух раз. Память O(1): числа переставляются в том же массиве, второго не нужно.

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

Решить на LeetCode ↗

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