LeetCode 189. 轮转数组
题目描述
题意分析
将数组整体向右轮转非负整数
k个位置，原下标i的元素应移动到(i + k) % n，越过末尾的元素从开头继续排列。所有元素都要保留，返回方式是在调用方传入的原数组上完成修改。向右转一整圈会回到原状，因此有效位移是
k % n。题目要求尽量给出至少三种方法，并尝试常数额外空间：下面依次说明三次反转、辅助数组和环状替换，其中反转与环状替换都满足常数空间。
解法：三次反转
核心思路
[!blue]
先将
k对长度取模，再把数组分成前n - k项组成的A和末尾k项组成的B。右轮转的目标就是把A + B变成B + A，同时保持每一段内部原来的顺序。整体反转会同时交换两段的位置和各段内部的顺序，结果变成
reverse(B) + reverse(A)。再分别反转前k项与剩余部分，各段内部顺序恢复，段的位置却不再改变，于是恰好得到目标B + A。每次反转都用两个下标从区间两端向中间交换，已经交换过的两端已经在最终位置，继续缩小尚未处理的区间即可。只需要一个交换临时变量，不会另外保存整个数组。
三个调用都使用闭区间。
k = 0时，前半区间为[0, -1]，交换循环不会执行；其余两次完整反转相互抵消，数组仍保持原状。代码还在取模前保留了空数组判断，避免对零取模。
解题步骤
- 数组为空时直接返回；否则令
k %= n。- 反转闭区间
[0, n - 1]，交换两段的位置。- 反转
[0, k - 1]，恢复移到前面的原后段顺序。- 反转
[k, n - 1]，恢复移到后面的原前段顺序，原数组修改完成。
代码实现
class Solution {
public void rotate(int[] nums, int k) {
if (nums.length == 0) {
return;
}
k %= nums.length;
// 先交换两段的位置，再分别反转两段恢复各自内部顺序。
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
int value = nums[left];
nums[left] = nums[right];
nums[right] = value;
left++;
right--;
}
}
}
func rotate(nums []int, k int) {
if len(nums) == 0 {
return
}
k %= len(nums)
// 先交换两段的位置，再分别反转两段恢复各自内部顺序。
reverse(nums, 0, len(nums)-1)
reverse(nums, 0, k-1)
reverse(nums, k, len(nums)-1)
}
func reverse(nums []int, left int, right int) {
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
复杂度分析
- 时间复杂度：$O(n)$，三次反转涉及的区间长度之和为
2n，每次都在线性时间内完成。- 空间复杂度：$O(1)$，只保存下标与交换用的临时值。
关键点总结
[!green]
- 右轮转可以看成把最后
k个元素组成的整段搬到开头。- 整体反转负责换段，局部反转负责恢复段内顺序。
- 先对长度取模，去掉不影响结果的完整圈数。
- 反转函数和调用处都采用闭区间，空区间自然不执行交换。
解法：辅助数组按目标下标搬移
核心思路
[!blue]
原下标
i的元素右移后去往(i + k) % n。新建一个等长数组，逐个把原元素写入目标下标即可。不同原下标取模后的目标位置不会相同，所以每个位置恰好被写入一次，没有冲突或遗漏。搬移过程中只读取原数组，所有写入都发生在辅助数组，因此不会覆盖尚未读取的旧元素。最后必须把辅助数组内容复制回原数组；只让局部形参指向辅助数组，不会改变调用方持有的那块数组内容。
解题步骤
- 空数组直接返回，否则将
k对长度取模。- 创建等长辅助数组，遍历原下标
i，写入result[(i + k) % n] = nums[i]。- 将辅助数组完整复制回
nums。
代码实现
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n == 0) {
return;
}
k %= n;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[(i + k) % n] = nums[i];
}
System.arraycopy(result, 0, nums, 0, n);
}
}
func rotate(nums []int, k int) {
n := len(nums)
if n == 0 {
return
}
k %= n
result := make([]int, n)
for i, value := range nums {
result[(i+k)%n] = value
}
copy(nums, result)
}
复杂度分析
- 时间复杂度：$O(n)$，一次按下标搬移、一次复制回原数组。
- 空间复杂度：$O(n)$，保存等长辅助数组；该方法完成原数组修改，但不满足常数额外空间的进阶要求。
关键点总结
[!green]
- 直接使用目标下标公式，辅助空间负责避免覆盖旧数据。
- 下标映射是一一对应关系，每个元素恰好搬到一个位置。
- 最后复制回原数组，确保调用方能观察到轮转结果。
解法：环状替换
核心思路
[!blue]
仍按
i → (i + k) % n搬移，但用一个临时变量代替整个辅助数组。从某个start出发，先保存当前位置的旧值，把它写入目标位置；覆盖之前再保存目标位置的旧值，作为下一轮要搬运的元素。这样沿目标下标继续前进，始终有一个临时值接住被覆盖的数据。这个下标映射会把所有位置分成若干个环。沿同一环移动最终会回到
start，此时本环所有位置都已经放好，原起点被最后一个元素填上，本轮可以结束。不能在此时就直接返回，因为一个环未必包含全部位置。设
g = gcd(n, k)。沿下标不断增加k，每个环的长度为n / g，共有g个环；同一环里的下标对g的余数相同。因此依次从start = 0、1、…出发时，在前g个起点处理的是不同环，不需要额外的访问数组。代码用
moved累计已经放好的位置数。每写入一个目标位置就加一，处理完一个环后从下一个起点继续，累计达到n就结束，因此也不必实际计算最大公约数。位移为零时，每个位置单独成环，同样能自然终止。
解题步骤
- 空数组直接返回，否则归一化
k，令累计搬移数moved = 0。- 从当前
start保存起点旧值，用current记录临时值原本所在的位置。- 计算
next = (current + k) % n，先保存nums[next]，再把临时值写入这里。- 将保存的旧值作为新的临时值，令
current = next，并增加搬移计数。- 回到本轮
start时结束这个环；若还未搬完n个位置，就从下一个起点继续。
代码实现
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n == 0) {
return;
}
k %= n;
int moved = 0;
for (int start = 0; moved < n; start++) {
int current = start;
int previous = nums[start];
do {
int next = (current + k) % n;
int displaced = nums[next];
nums[next] = previous;
previous = displaced;
current = next;
moved++;
} while (current != start);
}
}
}
func rotate(nums []int, k int) {
n := len(nums)
if n == 0 {
return
}
k %= n
moved := 0
for start := 0; moved < n; start++ {
current := start
previous := nums[start]
for {
next := (current + k) % n
displaced := nums[next]
nums[next] = previous
previous = displaced
current = next
moved++
if current == start {
break
}
}
}
}
复杂度分析
- 时间复杂度：$O(n)$，每个环处理各自的位置，累计恰好搬移
n个元素。- 空间复杂度：$O(1)$，只保存当前位置、计数和搬移过程中的临时值。
关键点总结
[!green]
- 每次覆盖之前保存旧值，沿目标下标把被替换的元素继续送走。
- 回到起点只表示一个环处理完，累计搬移数达到
n才表示整个数组处理完。- 环的结构保证顺次选取起点不会重复处理已完成的环，无需额外访问标记。
- 三次反转通过整段重排完成轮转，环状替换则直接把每个元素送到目标下标。
易错点总结
[!yellow]
- 取模前没有处理空数组，会发生除零；本实现保留了这一边界判断。
- 把右移的目标位置写成左移规则，或忘记对长度取模，会得到错误方向或越界下标。
- 三次反转的端点应为
[0, n - 1]、[0, k - 1]、[k, n - 1]，不能混用右开区间。- 辅助数组完成后只重新给形参赋值，没有复制回原数组，调用方就看不到修改。
- 环状替换覆盖目标位置前不保存旧值，会丢掉下一步还需要搬运的元素。
- 只处理从下标零出发的一个环，可能遗漏其他循环；要累计完成所有
n个位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 61. 旋转链表 | 中等 | 旋转量都需对长度取模，链表通过接环断开，本题通过反转或循环搬移。 |