将包含* n* 个元素的数组向右旋转 *k *步。
例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。
注意:
尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。
提示:
要求空间复杂度为 O(1)
分析：
题意明显，就是数组内换位置。这里可能会有一个误区，空间复杂度要求为O(1)，并不是说不能创建数组，可以创建，但不能让创建的数组超过常数级别的空间复杂度。另外K可以通过取模运算，避免重复的换位操作。各位小伙伴，八仙过海，各显神通，拿下这道题吧！
接下来给出 4 种Java的解法，推荐度由低到高。
解法一：
优点：不用创建新数组。
缺点：太耗时，平台可能因为耗时太长而不通过。
思路：向右旋转K步可以分解为做K次K=1的旋转，那么可以让每个元素都向右移1位，最后1位移到开头位置，总共做k次这种全局移位即可。
Java代码如下：
public void rotate(int[] nums, int k) {
if (nums.length == 0 || nums.length == 1) {
return;
}
k = k % nums.length;
int currentCache = 0;
int targetCache = 0;
for (int i = 0; i < k; i++) {
for (int j = 0; j < nums.length; j++) {
if (j == nums.length - 1) {
nums[0] = currentCache;
break;
}
if (j == 0) {
currentCache = nums[j];
}
targetCache = nums[j + 1];
nums[j + 1] = currentCache;
currentCache = targetCache;
}
}
}
解法二：
优点：速度比解法一快很多。
缺点：需要新创建数组。
思路：这是最容易想到的方法，创建一个新数组，内容和原数组保持一致，然后将新数组的每一个元素按照脚标加k的新脚标放入原数组对应的位置。这样原数组就完成了新赋值。
Java解答如下：
public void rotate(int[] nums, int k) {
if (nums.length == 0 || nums.length == 1) {
return;
}
int[] newNums = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
newNums[i] = nums[i];
}
int index;
for (int i = 0; i < nums.length; i++) {
index = (i + k) % nums.length;
nums[index] = newNums[i];
}
}
解法三：
优点：速度非常快。
缺点：需要创建一个比原数组长的新数组。
思路：由于是向右旋转k位，原数组的 [0, length - k) 个元素将向后移动k位，最终移到数组[k, length)的位置；而原数组的 [length - k, length) 个元素将会移动到数组的前面，占据了[0, k)的位置。
由此，创建一个新的长度是 length + k 的新数组，让新数组 [k, length + k) 的位置存放原数组的 [0, length)；然后让新数组的 [0, k) 位存放原数组的 [length - k, length) 位。此时新数组的 [0, length) 就是原数组旋转之后的结果，再依次拷贝回原数组即可。
Java解答如下：
public void rotate(int[] nums, int k) {
int length = nums.length;
if (length == 0 || length == 1) {
return;
}
k %= length;
int[] newnums = new int[length + k];
System.arraycopy(nums, 0, newnums, k, length);
System.arraycopy(nums, length - k, newnums, 0, k);
System.arraycopy(newnums, 0, nums, 0, length);
}
解法四：
优点：不用创建新数组，速度很快。
缺点：仅仅比解法三慢几毫秒。
思路：这里利用了一个小技巧。把原数组脚标为 0和length - 1的两个元素交换位置，再把 1和length - 2两个元素交换，依次类推直到整个数组顺序正好反转（原本{1,2,3,4,5,6}变成{6,5,4,3,2,1}），再把当前的数组 [0,k) 和 [k,length) 的位置分别进行反转，就这样，利用三次位置反转，就可以得到数组向右旋转k位的结果。
reverse()方法能把传入的数组arr的 [start, end] 的位置元素一一调换。
Java解答如下：
public void rotate(int[] nums, int k) {
int length = nums.length;
if (length == 0 || length == 1) {
return;
}
k %= length;
reverse(nums, 0, length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, length - 1);
}
private void reverse(int[] arr, int start, int end) {
while (start < end) {
arr[start] = arr[start] + arr[end];
arr[end] = arr[start] - arr[end];
arr[start] = arr[start] - arr[end];
start += 1;
end -= 1;
}
}
网友评论