Rotate Array
给你一个整数数组 nums 和一个数字 k。将数组向右旋转 k 步：每一步中，每个值都向右移动一位，最后一个值会绕回到最前面。返回旋转后的数组。
k 可能远大于数组的长度。
函数
- numsinteger-array
- 要旋转的整数数组
- kinteger
- 向右旋转几步
- 返回值integer-array
- nums 向右旋转 k 步
约束条件
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 1040 ≤ k ≤ 109
示例
- 输入
- nums = [4, 9, 1, 6, 3]k = 2
- 输出
- [6, 3, 4, 9, 1]
- 解释
- 向右移动两步后，最后两个值 6 和 3 会绕到前面。其他三个值向右移动两位，并保持原来的顺序：
[6, 3, 4, 9, 1]。
- 输入
- nums = [10, 20, 30]k = 7
- 输出
- [30, 10, 20]
- 解释
- 每 3 步，长度为 3 的数组都会回到起点，所以 7 步相当于 7 除以 3 取余后的 1 步。一步会把 30 移到最前面。
- 输入
- nums = [-5, 8]k = 4
- 输出
- [-5, 8]
- 解释
- 4 mod 2 = 0，所以经过 4 步后，每个值都回到了原来的位置，数组也恢复原样。
进阶
你能把每个值直接移到 (i + k) mod n，同时把被替换的值继续向后移动，从而原地旋转吗？这样会形成多少个循环？
提示
逐个打开提示，每个都会多透露一点。
长度为
n的数组经过n步后会恢复到初始顺序。当k为 10^9 时，实际上有多少步是有效的？旋转后，最后的
k mod n个值会移到数组前面，其余值跟在后面，每个部分都保持原来的顺序。索引i处的值会移到哪里？反转整个数组会把最后一个块移到前面，但两个块都会变成倒序。再分别反转一次每个块，就能恢复它们的顺序。每次反转时，两个索引会朝彼此移动。
题解
每经过 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 和 B，其中 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 中，当
k = 7且n = 3时，nums[-k:] + nums[:-k]会返回未改变的数组，因为两个切片都在数组边界处结束。 - 反转顺序错误。先反转两个块，最后再反转整个数组，得到的是向左旋转。
- 块的边界差一位：第一个块在索引
k-1处结束，第二个块从k开始。在 Lua 和 R 中，索引从 1 开始，因此两个块分别是1..k和k+1..n。
常见问题3
Rotate Array 的时间复杂度是多少？
复制方法和三次反转的时间复杂度都是 O(n)，因为每个值只会被移动固定次数。先用 k mod n 缩小 k，就能避免巨大的 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]