数组的右旋转是指将数组中的元素向右移动指定的步数,超出数组长度的元素会从数组的最左侧重新开始插入。通过切片的方式可以实现这一操作,这种方法简洁且易于理解。
假设我们有一个数组 arr
和一个整数 k
,表示需要向右旋转 k
步。可以通过以下步骤实现:
n
步和旋转 n % len(arr)
步是等价的。def right_rotate(arr, k):
n = len(arr)
k = k % n # 计算实际需要旋转的步数
return arr[-k:] + arr[:-k]
# 示例
arr = [1, 2, 3, 4, 5]
k = 2
result = right_rotate(arr, k)
print(result) # 输出: [4, 5, 1, 2, 3]
问题:当数组非常大时,切片操作可能会导致内存使用过高。 解决方法:
def right_rotate_inplace(arr, k):
n = len(arr)
k = k % n
reverse(arr, 0, n - 1)
reverse(arr, 0, k - 1)
reverse(arr, k, n - 1)
def reverse(arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
# 示例
arr = [1, 2, 3, 4, 5]
k = 2
right_rotate_inplace(arr, k)
print(arr) # 输出: [4, 5, 1, 2, 3]
通过这种方式,可以在不增加额外内存开销的情况下实现数组的右旋转。
领取专属 10元无门槛券
手把手带您无忧上云