0
0
0
LeetCode189-轮转数组

文章摘要
|

我说实话,我第一反应是 时空 复杂度为O(n)的新开数组原地copy,但他的问题也如下所示
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
int[] newArr = new int[n];
for(int i = 0; i < k; i++){
newArr[i] = nums[n - k + i];
}
for(int i = 0; i < n - k; i++){
newArr[k + i] = nums[i];
}
System.arraycopy(newArr,0,nums,0,n);
}
}
内存消耗简直爆炸了,这个解法我估计给谁看都得眼前一黑,这啥啊,你小子只会枚举是不,巴拉巴拉。。。。。。
同时这题题目鼓励我们去尝试下空间复杂度为O(1)的解法。
等等,先不考虑内存了,有个非常牛逼的思路,不行,我要先把这个思路写下
nums = "----->-->"; k =3
result = "-->----->";
reverse "----->-->" we can get "<--<-----"
reverse "<--" we can get "--><-----"
reverse "<-----" we can get "-->----->"
this visualization help me figure it out :)class Solution {
public void rotate(int[] nums, int k) {
k=k%nums.length;
reverse(nums,0,nums.length-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.length-1);
}
private void reverse(int[] nums,int a,int b){
int i=a,j=b;
while(i<j){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
i++;
j--;
}
}
}这是主播看到外网一位大神的解法以及底下置顶评论的可视化,太牛逼了这个思路和可视化,reverse为c++语法,在这里我们仅需要自己实现reverse便可直接结束战斗,没有什么高深的算法,但是很优雅,通过三次反转原地进行数组的轮转移动,这才是真正的算法。
