Rotate Array

Q: Что происходит, когда k больше длины массива?

Каждые n шагов массив возвращается к исходному порядку, поэтому важны только k mod n шагов. Повернуть [10, 20, 30] на 7 позиций — то же самое, что повернуть его на 1 позицию, в результате чего получится [30, 10, 20] . Когда k кратно n , массив не меняется.

Q: Как выполнить циклический сдвиг массива влево?

Левый поворот на k — это правый поворот на n - (k mod n) . При использовании разворотов разверни сначала первые k mod n значений, затем остальные, а потом весь массив. В обоих случаях время выполнения — O(n).

СреднеМассивы и строки Два указателя

+10

Дан массив целых чисел nums и число k. Выполните циклический сдвиг массива вправо на k шагов: за один шаг каждое значение перемещается на одну позицию вправо, а последнее значение переносится в начало. Верните сдвинутый массив.

k может быть намного больше длины массива.

Функция

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: массив целых чисел, который нужно повернуть
kinteger: на сколько шагов повернуть направо
Возвращаетinteger-array: числа, циклически сдвинутые вправо на k шагов

Ограничения

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Примеры

Ввод: nums = [4, 9, 1, 6, 3]k = 2
Вывод: [6, 3, 4, 9, 1]
Пояснение: Два шага вправо переносят последние два значения, 6 и 3, в начало. Остальные три значения перемещаются на два места вправо и сохраняют свой порядок: [6, 3, 4, 9, 1].

Дополнительный вопрос

Можешь ли ты выполнить циклический сдвиг на месте, перемещая каждое значение напрямую в (i + k) mod n и продолжая перемещать вытесненное им значение? Сколько циклов для этого потребуется?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждые n шагов массив возвращается в исходное положение, поэтому сначала сократите k, которое может быть равно 10^9, до k mod n. Затем запишите каждое значение сразу в его конечный индекс во втором массиве или добейтесь того же результата внутри массива с помощью трёх разворотов и дополнительной памяти O(1).

Скопируйте каждое значение в новый индекс

Идея

После k шагов значение с индексом i находится по индексу (i + k) mod n, поэтому запиши его сразу туда, не выполняя шаги. Сначала сократи k до k mod n: поворот на n возвращает каждое значение на прежнее место, поэтому при k = 7 и n = 3 остаётся выполнить всего один шаг.

За один проход размещаются все n значений: время O(n), плюс память O(n) для результата. Таким способом нельзя записывать значения непосредственно в nums, потому что каждая запись перезапишет значение, которое ты ещё не переместил.

Алгоритм

Присвойте n длину nums и замените k на k mod n.
Создайте результирующий массив длины n.
Для каждого индекса i сохраните nums[i] в result[(i + k) mod n].
Верните результат.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Три разворота на месте

Идея

Разделите массив на A — первые n-k значений — и B — последние k значений. Повернутый массив — это B, за которым следует A, причём каждый блок сохраняет прежний порядок. Переворот всего массива меняет порядок блоков и порядок элементов внутри каждого из них: поэтому сначала идёт B, но в обратном порядке, и то же самое происходит с A. Повторный переворот каждого блока восстанавливает исходный порядок элементов в нём.

Для [4, 9, 1, 6, 3] и k = 2: переворот всего массива даёт [3, 6, 1, 9, 4], переворот первых двух элементов даёт [6, 3, 1, 9, 4], а переворот последних трёх — [6, 3, 4, 9, 1].

Каждое значение меняется местами не более двух раз, поэтому время работы составляет O(n), а для дополнительной памяти требуются лишь несколько переменных-индексов (в R — O(n), поскольку при изменении вектора вспомогательной функцией для переворота создаётся его копия).

Алгоритм

Задай n равным длине nums и замени k на k mod n.
Разверни весь массив, индексы от 0 до n-1.
Разверни первый блок, индексы от 0 до k-1.
Разверни второй блок, индексы от k до n-1.
Верни nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Ловушки и крайние случаи

Забыть о k mod n. При k = 10^9 вращение по шагам никогда не завершится, а разворот первых k значений приведёт к чтению далеко за концом массива.
Срезы без взятия по модулю. В Python выражение nums[-k:] + nums[:-k] при k = 7 и n = 3 возвращает массив без изменений, потому что оба среза заканчиваются на границе массива.
Разворот в неправильном порядке. Если сначала развернуть два блока, а в конце весь массив, получится левый циклический сдвиг.
Ошибка на единицу у границы блока: первый блок заканчивается на индексе k-1, а второй начинается с k. В Lua и R, где отсчёт начинается с 1, блоки имеют диапазоны 1..k и k+1..n.

Частые вопросы3

Какова временная сложность алгоритма Rotate Array?

O(n) как для подхода с копированием, так и для трёх разворотов, поскольку каждое значение перемещается постоянное число раз. Сначала уменьшая k с помощью k mod n, мы не даём огромному k повлиять на сложность. Вместо этого поворот на один шаг за раз стоит O(n × k).

Что происходит, когда k больше длины массива?

Каждые n шагов массив возвращается к исходному порядку, поэтому важны только k mod n шагов. Повернуть [10, 20, 30] на 7 позиций — то же самое, что повернуть его на 1 позицию, в результате чего получится [30, 10, 20]. Когда k кратно n, массив не меняется.

Как выполнить циклический сдвиг массива влево?

Левый поворот на k — это правый поворот на n - (k mod n). При использовании разворотов разверни сначала первые k mod n значений, затем остальные, а потом весь массив. В обоих случаях время выполнения — O(n).

def rotate(nums, k):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

nums = [4, 9, 1, 6, 3]
k = 2

Ожидаемый вывод

[6, 3, 4, 9, 1]