将数组向右旋转 k 步

Question

我有一个任务，给定一个整数数组nums，将数组向右旋转k步，其中k是非负数。

例如：
输入：nums = [1,2,3,4,5,6,7]，k = 3

输出：[5,6,7,1,2,3,4]

解释：
向右旋转1步：[7,1,2,3,4,5,6]
向右旋转2步：[6,7,1,2,3,4,5]
向右旋转3步：[5,6,7,1,2,3,4]

我想知道如何在时间复杂度为O(n)且空间复杂度尽可能为O(1)的情况下解决这个问题（如果可能的话）。

附注：我已经知道时间复杂度为O(kn)且空间复杂度为O(1)的解决方案。

Richard Garside · Answer

你可以使用一个临时变量来存储移动的值，并通过索引从一个目标位置遍历到另一个目标位置（利用取模运算来处理列表长度的循环移位）：

def rotInPlace(A, k):
    v, i = A[0], k
    for _ in A:
        v, A[i] = A[i], v
        i = (i + k) % len(A)

# 示例
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3

rotInPlace(nums, k)

print(nums)
# 输出：[5, 6, 7, 1, 2, 3, 4]

Darrel Miller · Answer

def rotate(lst, k):
    return lst[-k:] + lst[:len(lst)-k]