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

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

---

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位，这样就实现数组翻转。

时间复杂度：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位置。但是我们要注意的两个边界条件就是有可能会产生环，无限在那几个值之间转移，还有就是替换的总次数需要统计，然后跳出循环，不然就会再次执行.


这是有可能发生的情况，所以我们需要把两种可能都考虑到
时间复杂度：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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。