问题描述
LeetCode 189 题要求将一个数组向右旋转 k 步，其中 k 是非负数。
例如，输入 nums = [1,2,3,4,5,6,7] 和 k = 3，输出应为 [5,6,7,1,2,3,4]。
这是一个常见的数组操作问题，可以通过多种方法解决。本文将分析三种主要的解法。
解法一：使用额外数组
思路
最直观的方法是创建一个新的数组，然后将原数组中的每个元素 nums[i] 放入新数组的正确位置 (i + k) % n。最后，将新数组的内容复制回原数组。为了优化空间，我们可以先复制原数组，然后直接在原数组上根据复制数组的值进行放置。
代码 (Java)
import java.util.Arrays;
class Solution {
// create new int[] nums2
public void rotate(int[] nums, int k) {
int n = nums.length;
// k 可能大于 n，取模获取实际有效旋转步数
k = k % n;
if (k == 0) return; // 旋转 0 步或 n 的整数倍步，数组不变
int[] nums2 = Arrays.copyOf(nums, n); // 复制原数组
for (int i = 0; i < n; i++) {
int rotatedIndex = (i + k) % n; // 计算旋转后的索引
nums[rotatedIndex] = nums2[i]; // 将复制数组的元素放到原数组的正确位置
}
}
}
分析
- 优点: 逻辑简单，易于理解和实现。
- 缺点: 需要额外的 O(n) 空间来存储数组副本。
- 时间复杂度: O(n)。
Arrays.copyOf需要 O(n)，循环放置元素也需要 O(n)。 - 空间复杂度: O(n)。需要一个大小为 n 的额外数组
nums2。
解法二：数组反转
思路
这是一种非常巧妙的 O(1) 空间复杂度的解法。通过三次数组反转操作可以实现旋转：
- 反转整个数组:
[1,2,3,4,5,6,7]->[7,6,5,4,3,2,1] - 反转前 k 个元素:
[7,6,5]->[5,6,7]，数组变为[5,6,7,4,3,2,1] - 反转后 n-k 个元素:
[4,3,2,1]->[1,2,3,4]，数组变为[5,6,7,1,2,3,4]
这样就得到了最终结果。
代码 (Java)
class Solution {
// rotate nums using reverse
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n; // 处理 k >= n 的情况
if (k == 0) return;
// 三次反转
reverse(nums, 0, n - 1); // 1. 反转整个数组
reverse(nums, 0, k - 1); // 2. 反转前 k 个元素
reverse(nums, k, n - 1); // 3. 反转后 n-k 个元素
}
// 辅助函数：反转数组指定范围内的元素
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
分析
- 优点: 空间复杂度为 O(1)，原地修改数组。效率高。
- 缺点: 相较于方法一，逻辑稍显不直观，需要理解反转操作如何实现旋转。
- 时间复杂度: O(n)。每个元素最多被移动（交换）两次。
reverse函数对其范围内的元素进行线性扫描。总时间为 O(n) + O(k) + O(n-k) = O(2n) = O(n)。 - 空间复杂度: O(1)。只需要常数空间存储临时变量
temp和索引。
解法三：循环替换
思路
这种方法也是原地旋转，尝试直接将每个元素放到它最终的位置上。从 start = 0 开始，将 nums[start] 放到 (start + k) % n 的位置，然后将被替换掉的元素放到它应该去的位置 ((start + k) + k) % n，如此循环下去，直到回到 start 位置。
一个潜在的问题是，如果 n 和 k 的最大公约数 gcd(n, k) > 1，一次循环可能无法访问所有元素（会提前回到 start）。例如 n=6, k=2，从 0 开始会访问 0 -> 2 -> 4 -> 0，而 1, 3, 5 未被访问。为了解决这个问题，我们需要进行 gcd(n, k) 次这样的循环。代码中使用 count 变量记录移动的总元素数量，外层循环 for(int start = 0; count < n; start++) 确保当一个循环结束后（current == start），如果 count < n，则从下一个 start 索引开始新的循环，直到所有 n 个元素都被移动。
代码 (Java)
class Solution {
// rotate using cyclic replacements
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
if (k == 0) return;
int count = 0; // 记录已放置到最终位置的元素数量
for (int start = 0; count < n; start++) {
int current = start; // 当前元素的索引
int prevValue = nums[start]; // 需要被移动到下一个位置的元素值
do {
int nextIndex = (current + k) % n; // 计算目标位置
int temp = nums[nextIndex]; // 暂存目标位置的原有值
nums[nextIndex] = prevValue; // 将 prevValue 放到目标位置
prevValue = temp; // 更新 prevValue 为被替换出来的值
current = nextIndex; // 移动到下一个位置
count++; // 移动了一个元素
} while (current != start); // 当回到起始位置时，一个循环结束
// 如果 count < n，外层循环 start++ 进入下一个起始点
}
}
}
分析
- 优点: 空间复杂度为 O(1)，原地修改。
- 缺点: 逻辑最为复杂，特别是处理
gcd(n, k) > 1的情况，do-while循环和count、start的配合需要仔细理解。 - 时间复杂度: O(n)。虽然有嵌套循环结构，但
count变量确保每个元素只被访问和移动一次。 - 空间复杂度: O(1)。只需要常数空间存储
count,start,current,prevValue,temp等变量。
总结与比较
| 解法 | 时间复杂度 | 空间复杂度 | 实现复杂度 | 优点 | 缺点 |
|---|---|---|---|---|---|
| 额外数组 | O(n) | O(n) | 低 | 简单直观 | 空间开销大 |
| 数组反转 | O(n) | O(1) | 中 | 空间 O(1)，代码相对简洁 | 思路稍不直观 |
| 循环替换 | O(n) | O(1) | 高 | 空间 O(1)，原地完成 | 逻辑复杂，不易实现 |
选择建议:
- 如果内存限制宽松，追求快速实现和易理解，解法一（额外数组） 是不错的选择。
- 在大多数要求 O(1) 空间复杂度的场景下（如面试、竞赛），解法二（数组反转） 是最优选，它在效率和实现难度之间取得了很好的平衡。
- 解法三（循环替换） 也是 O(1) 空间的有效方法，但其复杂性使得它在实际编码中不如解法二常用，更多用于理解算法思想。
这三种方法覆盖了解决旋转数组问题的主要思路，理解它们有助于掌握不同的数组操作技巧。