1、题目描述
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [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:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1)的原地算法。
2、解法
①：整体移动法
以从下标0开始长度为(size - k)的数组集合整体移动k个单位，后面数字的依次往前移动,例如题目中举出的第1个示例来说，
[1,2,3,4,5,6,7]移动k = 3，也就是以第0个开始长度为（7 - 3 = 4）的数组集合([1,2,3,4])移动3个长度单位
第一次移动： [7,1,2,3,4,5,6]
第二次移动： [6,7,1,2,3,4,5]
第三次移动： [5,6,7,1,2,3,4]
public void rotate(int[] nums, int k) {
k = k % nums.length;
if (k == 0)return;
for(int j = 0;j <k;j++){
for (int i = j+(nums.length - 1 - k);i>=j;i--){
swapNum(nums,i,i+1);
}
}
}
public void swapNum(int[] num,int pre,int next){
if (next > num.length - 1||next <0) return;
num[pre] = num[pre]^num[next];
num[next] = num[pre]^num[next];
num[pre] = num[pre]^num[next];
}
这是正常的思路的解法，但是题目要求是O(1)的时间复杂度，而这个解法的时间复杂度却是O(n^2)，因此不符合题目要求，这也有了下面的两种解法。
②：翻转法
这种解法需要画一个图来说明，请看下图。
图(1):翻转法原理
哈哈,在这里请忽略下字体不美观的因素，还是来关注下主要算法核心，由此图可以得出，可以分3步走，第一次是从0到(size - k - 1)的翻转，第二次是（size - k）到size的翻转，第三次是整体的翻转。
第一次翻转： [4,3,2,1,5,6,7]
第二次翻转： [4,3,2,1,7,6,5]
第三次翻转： [5,6,7,1,2,3,4]
代码如下:
public void rotate(int[] nums, int k) {
k %= nums.length;
int i = nums.length-k;
reverse(nums, 0, i-1);
reverse(nums,i,nums.length-1);
reverse(nums,0,nums.length-1);
}
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--;
}
}
③：扩展数组法（以空间换时间）
还是以[1,2,3,4,5,6,7]这个数组为例，可以再增加一个相同的数组成为[1,2,3,4,5,6,7,1,2,3,4,5,6,7]，当移动k = 3个时，可以从这个数组得知是从下标(size - k)起长度为size的数组[5,6,7,1,2,3,4]
代码如下:
public void rotate(int[] nums, int k) {
k = k % nums.length;
if (k == 0)return;
int[] numscopy = new int[nums.length * 2];
for (int i = 0; i < nums.length * 2; i++) {
numscopy[i] = nums[i%nums.length];
}
for (int i = nums.length - k;i<2 * nums.length - k;i++){
nums[i + k - nums.length] = numscopy[i];
}
}
经测试，可行！