189. 旋转数组
题目描述
方法一:使用暴力法
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] second = new int[n];
for(int i=0; i<n; i++){
second[(i + k) % n] = nums[i];
}
System.arraycopy(second, 0, nums, 0, n);
//注意这里不能使用nums = Arrays.copy(second, n);的方式
}
}
方法二:翻转法
- 可以采用三次翻转的方法解决这个问题。
- 第一次翻转可以将后k个元素全部移动到前k的位置,只不过位置和要求的不是一一对应的。
- 第二次翻转可以将前k个元素的位置调正。
- 第三次翻转把后面的位置调整正确。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n-1);
reverse(nums, 0, k - 1);
reverse(nums, k, n-1);
}
public void reverse(int[] nums, int from, int to){
while(from < to){
int temp = nums[from];
nums[from] = nums[to];
nums[to] = temp;
from++;
to--;
}
}
}