🖥 Задача о циклическом сдвиге

Циклический сдвиг массива — это когда каждый элемент кроме последнего сдвигается вправо, а последний элемент массива становится первым.

На вход подаются массив A и целое число K. Сделайте циклический сдвиг входного массива K раз и верните получившийся массив.

Например, для данных:

A = [2, 5, 1, 4, 6]
K = 3

Циклический сдвиг должен быть выполнен трижды:

[2, 5, 1, 4, 6] -> [6, 2, 5, 1, 4]
[6, 2, 5, 1, 4] -> [4, 6, 2, 5, 1]
[4, 6, 2, 5, 1] -> [1, 4, 6, 2, 5]

И программа должна вернуть

[1, 4, 6, 2, 5]

Если K = 0, то сдвиг не делается.

Для K = 5:

[2, 5, 1, 4, 6] -> [2, 5, 1, 4, 6]

Наивное решение:

1. Определяем, что такое ротировать массив один раз.
2. Делаем это K раз.

def rotate(A, K):
""" Rotates a list K times """
if not A:
return []

for i in range(K):
A = rotate_once(A)
return A


def rotate_once(A):
""" Rotates a list once """
A.insert(0, A[-1])
del A[-1]
return A

Это решение не оптимальное, потому что каждый insert() передвигает все элементы исходного списка. Также оно не учитывает, что после len(A) ротаций список возвращается в исходное состояние.

Индексы элементов в новом массиве несложно рассчитать аналитически, поэтому:

def rotate(A, K):
""" Rotates a list K times """
result = []
if K == 0:
return A
else:
for i in range(len(A)):
new_index = (i - K) % len(A)
result.append(A[new_index])
return result

Это лучше, потому что
▪ результат получается за один проход
▪ и время работы не увеличивается на больших K.

@python_job_interview