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便可直接结束战斗,没有什么高深的算法,但是很优雅,通过三次反转原地进行数组的轮转移动,这才是真正的算法。

支持与分享

如果这篇文章对你有帮助,欢迎分享给更多人或者给予支持!

评论