轮转数组
Rotate Array
本机进度仅保存在当前浏览器
题目描述
给定一个整数数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。要求使用空间复杂度 O(1) 的原地算法。
示例：nums = [1, 2, 3, 4, 5, 6, 7]，k = 3，输出 [5, 6, 7, 1, 2, 3, 4]。
解题思路
- 观察结果结构：右旋 k 位后，数组由「后 k 个元素 + 前 n-k 个元素」拼接而成。
- 三次翻转技巧：先整体翻转，再分别翻转前 k 个与后 n-k 个元素，即得结果。
- 注意 k 可能大于数组长度，实际位移为 k mod n。
- 三次翻转共移动每个元素常数次，比循环移位的 O(n·k) 高效得多。
参考实现
查看参考实现Python · 建议先自行作答
def rotate(nums, k):
def reverse(l, r):
# 双指针原地翻转闭区间 [l, r]
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
n = len(nums)
k %= n
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)