【LC100】No189. 轮转数组
题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
提示:
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
进阶：
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例
示例 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:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]链接
思路
简单吗？如简单。
但看上去真的很简单。
解法一：用额外数组保存结果
对于数组元素 nums[i]，向右轮转 k 个位置后，其从下标 i 移动到 i + k 的位置。i + k 一旦超过数组长度，会重新从数组左端 0 的位置继续移动，我们可以通过对数组长度取余来找到这个新位置。
即，移动后的最终位置为 (i + k) % len，len为数组长度。
因此，我们使用一个额外数组，将每个元素保存到应该存放的新位置，最后复制给原数组 nums。
Q：为什么使用复制不使用直接复制
A：nums 在本题中通过方法形参传递进来，此时方法内的 nums 是原始引用的拷贝副本，只是和原始引用一样，指向同一个数组对象。
如果使用赋值，将 res 直接赋值给 nums，修改的也只是方法内 nums 这个引用指向了新的数组 res，原始引用处的指向不变。
但使用复制方法，修改对象内容，会影响到原始数组对象。
代码
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return;
}
int len = nums.length;
int[] res = new int[len];
for (int i = 0; i < len; i++) {
res[(i + k) % len] = nums[i];
}
// System.arraycopy(原数组, 原数组起始下标, 目标数组, 目标数组起始下标, 数组长度)
System.arraycopy(res, 0, nums, 0, len);
}
}时间复杂度：O(n)
空间复杂度：O(n)
解法二：原地翻转
很数学的思路，很数学。
在示例一中，要将 [1,2,3,4,5,6,7] 翻转成 [5,6,7,1,2,3,4]。
可以看出 567 移动到了 1234 的前面，这个我们可以通过翻转整个数组实现，即变为 [7,6,5,4,3,2,1]。
继续观察，我们需要将 765 翻转成 567，同时将 4321 翻转成 1234，最后所得结果即为题目所求。
有一个需要注意的点是，由于 k 可能大于数组长度，例如数组长度为 7，k 为 10，但对于此数组来说，轮转 7 次之后的结果和原数组一样。所以为了减少翻转次数，我们可以先对 k 在数组长度上取余。
即 k %= len。
代码
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return;
}
int len = nums.length;
k %= len;
reverse(nums, 0, len - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, len - 1);
}
private void reverse(int[] nums, int i, int j) {
while(i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
}时间复杂度：O(n)
空间复杂度：O(1)