力扣题目:
轮转数组
(需要看答案的uu可以直接跳到第三种解题思路,前两种是自己的思路,时间复杂度都太高。)
【1】分析 思路一:首先我们可以创建一个临时变量temp,将数组中最后一个值放入temp中, 然后依次将数组的值通过循环往后移动。
于是我们可以写出 下列代码:
class Solution {
public void rotate(int[] nums, int k) {
for(int j = 0; j < k;j++){
int temp = nums[nums.length-1];
for(int i = 1;i < nums.length; i++){
nums[nums.length - i] = nums[nums.length - (i+1)];
}
nums[0] = temp;
}
}
}
这样写代码是没有语法问题单,但是!这样写超过了题目所规定的时间复杂度。如下:
这是一件令人伤心的事情!T.T 5555
我们来换一种思路:
然后:我们会得到以下代码:
class Solution {
public void rotate(int[] nums, int k) {
for(int i = 0;i < k ;i++){
int[] arr1 = new int[nums.length];
arr1[0] = nums[nums.length - 1];
for(int j = 1;j < nums.length ;j++){
arr1[j] = nums[j-1];
}
for(int m = 0;m < nums.length; m++){
nums[m] = arr1[m];
}
}
}
}
很好。然后…
叒不对,我真是,555太难过了。我们再换种思路(官方提供):
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reserve(nums,0,n-1);
reserve(nums,0,k-1);
reserve(nums,k,n-1);
}
public void reserve(int[] nums,int start,int end){
for(int i = start,j = end;i < j;i++,j--){
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
不得不说,这种方法真的太妙啦。真是进了米奇妙妙屋了。