欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【leetcode】每日精选题详解之189旋转数组

程序员文章站 2022-06-07 12:52:47
...

        嗨,大家好,我是袁厨(因为酷爱做饭,所以自己考取了厨师证)。之前一直看大家写的博客,学到了很多东西。然后最近萌生了自己写的想法,将自己知道的分享给需要的同学。以后每天会为大家分享leetcode精选题目的各种题解和Python, JS, JQ, CSS, PHP, JAVA的一些小Demo。请大家关注我,一起交流学习吧。


题目描述

【leetcode】每日精选题详解之189旋转数组


暴力解法

做题思路

这个做题思路很简单,我们只需要双重循环即可,这种题解也是符合题目要求的,空间复杂度为O(1).我们只需要每次都将数组元素往后移动一位,然后移动K次即可,但是需要注意的是,我们应该先把数组最后一位存到临时变量里,等执行完一次之后,将其补到数组头部。

时间复杂度:O(n*k) 空间复杂度O(1)

题目代码

class Solution {
    public void rotate(int[] nums, int k) {
        //临界情况去除
         if( nums.length == 0 || k == 0 || nums.length == 1 || nums.length == k){
            return;
        }
        //K大于数组长度时,取余
        int t = k%nums.length;
        //循环K次
        for(int i = 0 ; i < k ; i++){
            //提前保留数组最后
            int temp = nums[nums.length-1];
            //将数组元素后移一位
            for(int j = nums.length-1 ;j >0 ;j--){
                nums[j]=nums[j-1];               
                
            }
            nums[0]= temp;//临时元素添加到头部
        }
    }
}

        


翻转法

做题思路

这个翻转法是执行速度最快,比较巧的一种做题思路,但是不是很容易想到,但是想到之后代码很简单。总题思路就是,先将整个数组进行翻转,然后翻转前K位,再翻转后面的n-k位,这样就实现数组翻转。
【leetcode】每日精选题详解之189旋转数组
时间复杂度:O(n) 空间复杂度O(1)

题目代码

class Solution {
    public void rotate(int[] nums, int k) {
        if( nums.length == 0 || k == 0 || nums.length == 1 || nums.length == k){
            return;
        } 
        int t = k % nums.length; 
        //反转数组     
        res(nums,0,nums.length-1);
        //旋转前K位
        res(nums,0,t-1);
        //旋转后面的n-k位
        res(nums,t,nums.length-1)}
    //构建反转函数,利用双指针方法
    public void res(int[] nums,int i ,int j){      
        int temp = 0;
        while(i<=j){
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

环状替换

做题思路

这个方法比较容易想到,但是代码不是很好写出来。总的思路就是,第1位移到第k位之后,然后再把第K位的值以后K+K位置。但是我们要注意的两个边界条件就是有可能会产生环,无限在那几个值之间转移,还有就是替换的总次数需要统计,然后跳出循环,不然就会再次执行.
【leetcode】每日精选题详解之189旋转数组
【leetcode】每日精选题详解之189旋转数组
这是有可能发生的情况,所以我们需要把两种可能都考虑到
时间复杂度:O(n) 空间复杂度O(1)

题目代码

public class Solution {
    public void rotate(int[] nums, int k) {
       //取余
       k = k % nums.length;
        int count = 0;
        //这里的临界条件时移动的次数,通过count来执行,start来记录每个环的开始值
        for (int start = 0; count < nums.length; start++) {           //记录开始时索引
            int index = start;
            //开始时的值,需要将他后移k位
            int pre = nums[index];
            //这里需要do while我们需要先执行一遍,再进行判断
            do{  //得出移动的位置索引
                int next = (index+k)%nums.length;
                //存好移动位置的值
                int temp = nums[next];
                //移动
                nums[next]=pre;
                //更换需要移动的值
                pre = temp;
                //更换需要移动的索引
                index = next;
                //记录移动次数,大家看for循环的条件
                count++;
            } while(index!=start);
        }
    }
}

总结

这个题目我感觉还蛮好的,学会三种方法可以应用到其他题目中。虽然是简单题,但是那个环状替换的代码难度比得上中等难度。

作者:LeetCode
链接:https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。