2021-02-23 13:00:20
Задача о циклическом сдвигеПредложила ее менти как тренировочную.
Циклический сдвиг массива — это когда каждый элемент кроме последнего сдвигается вправо, а последний элемент массива становится первым.
На вход подаются массив 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.
Очень радуюсь, когда получается у учеников!
5.8K viewsdaily_python_bot, edited 10:00
P
