 原地轮转)
题目说明
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置。题目要求原地修改数组。
例如：
输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]
思路：把右移拆成三次反转
数组长度记为 n。向右轮转 k 位后，原数组可以分为两段：
- 前半段：
nums[0:n-k] - 后半段：
nums[n-k:n]
目标是把后半段移到前面，同时保持两段内部的相对顺序。可以依次执行：
- 反转整个数组；
- 反转前
k个元素； - 反转剩余
n-k个元素。
以 [1,2,3,4,5,6,7]、k = 3 为例：
原数组： [1,2,3,4,5,6,7]
整体反转： [7,6,5,4,3,2,1]
反转前 3 项： [5,6,7,4,3,2,1]
反转剩余部分： [5,6,7,1,2,3,4]
注意先执行 k %= n。当 k 大于数组长度时，整轮移动不会改变数组，真正有效的位数只有余数部分。
Python 代码
class Solution:def rotate(self, nums: list[int], k: int) -> None:n = len(nums)k %= ndef reverse(left: int, right: int) -> None:while left < right:nums[left], nums[right] = nums[right], nums[left]left += 1right -= 1reverse(0, n - 1)reverse(0, k - 1)reverse(k, n - 1)
正确性说明
整体反转后，原数组末尾的 k 个元素被放到数组前面，但它们的顺序被反转；原数组前面的 n-k 个元素被放到后面，顺序同样被反转。再分别反转这两段，就能恢复各段内部原有顺序，因此最终结果恰好是向右轮转 k 位后的数组。
复杂度分析
- 时间复杂度：
O(n)。三个反转操作总共处理线性数量的元素。 - 空间复杂度：
O(1)。只使用常数个变量，符合原地修改要求。
易错点
- 忘记执行
k %= n，导致k > n时下标错误。 - 三次反转的区间写错。正确区间依次是
[0, n-1]、[0, k-1]、[k, n-1]。 - 题目要求原地修改，不需要返回新数组。
- 当
k = 0时，前两个反转会相互抵消，结果仍然正确。
面试表达
可以先说明使用额外数组能够直接完成，但空间复杂度为 O(n)；随后给出三次反转，将额外空间优化到 O(1)。重点解释“整体反转改变两段位置，局部反转恢复段内顺序”。