189. 轮转数组
1. 题目简介
难度：中等，原题链接：189. 轮转数组。
给定一个整数数组
nums，将数组中的元素向右轮转k个位置，其中k是非负数。
示例 1：
输入：
nums = [1,2,3,4,5,6,7], k = 3输出：
[5,6,7,1,2,3,4]向右轮转 1 步：
[7,1,2,3,4,5,6]向右轮转 2 步：
[6,7,1,2,3,4,5]向右轮转 3 步：
[5,6,7,1,2,3,4]
2. 问题分析
向右轮转 k 位，就是把末尾的 k 个元素移到开头，同时保持两部分各自的顺序。数组长度为 n 时，轮转 n 位会回到原样，所以先用 k %= n 去掉完整的轮转圈数。
2.1 模拟算法
可以用临时数组保存末尾的 k 个元素，再完成搬移：
- 保存末尾的
k个元素。 - 从后往前，把前
n - k个元素各右移k位。这个方向能避免覆盖尚未搬走的元素。 - 把临时数组中的元素写回开头的
k个位置。
这种方法需要 O(k) 的额外空间。
2.2 分段反转
题目还提出了空间上的进阶要求：
你可以使用空间复杂度为
O(1)的 原地 算法解决这个问题吗？
可以把数组分成前 n - k 个元素和后 k 个元素，分别反转两部分，再反转整个数组。最后一次反转会交换两部分的位置，同时恢复各自内部的顺序。
以 [1, 2, 3, 4, 5, 6, 7]、k = 3 为例：
- 分别反转
[1, 2, 3, 4]和[5, 6, 7]，得到[4, 3, 2, 1, 7, 6, 5]。 - 反转整个数组，得到
[5, 6, 7, 1, 2, 3, 4]。
也可以用下标验证。原下标 i < n - k 的元素，第一次反转后位于 n - k - 1 - i，整体反转后位于 i + k。后半段的元素最终位于 i + k - n。两种情况都符合向右轮转后的目标下标 (i + k) % n。
3. 代码实现
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - k - 1);
reverse(nums, n - k, n - 1);
reverse(nums, 0, n - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int tmp = nums[start];
nums[start++] = nums[end];
nums[end--] = tmp;
}
}
}
reverse 反转闭区间 [start, end]，三次调用分别对应前 n - k 个元素、后 k 个元素和整个数组。k 为 0 时，第二次调用的区间为空，start < end 不成立，不会改动数组。
4. 复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明