Leetcode-189. 旋转数组

题目描述
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。

分别描述五个方法的思路和运行结果
其中四和五为题解吸收
方法一直接模拟k次数组右移一位

方法二借助k长的数组保存后k个元素，然后右移k位，然后更新前k个元素

方法三在方法一的基础上先对k求余--保证k小于n

方法四多次翻转
先将整个数组进行反转，这样后k个元素可位于前k个位置
之后再分别将前k个元素翻转，后半部分也进行翻转

方法五环形数组
比如n=6，k=4
进行先将0移到4，记录4
再将4移到2，也就是将记录的值移到2
特殊情况：再移动的过程中，可能会陷入重复移动，所以需要记录下是否移动过
如果已经移动过，则指标右移。
一共需要一定n次

java代码参考

class Solution {
    //方法一：直接模拟k次的数组右移
    /*public void rotate(int[] nums, int k) {
        for(int i=0;i<k;i++){
            //模拟数组右移的过程
            int t=nums[nums.length-1];
            for(int j=nums.length-1;j>0;j--){
                nums[j]=nums[j-1];
            }
            nums[0]=t;
        }
    }*/
    //方法二：保存后k个数，然后数组右移k，然后再赋值前k个数字
    /*
    public void rotate(int[] nums, int k) {
        k=k % nums.length;
        int[] tmp=new int[k];
        //模拟数组右移k的过程
        for(int i=0;i<k;i++){
            tmp[i]=nums[nums.length-1-i];
        }
        for(int j=nums.length-1;j>=k;j--){
            nums[j]=nums[j-k];
        }
        for(int i=0;i<k;i++){
            nums[k-1-i]=tmp[i];
        }
    }*/
    //改进方法一：直接模拟k次的数组右移
    /*public void rotate(int[] nums, int k) {
        k=k % nums.length;
        for(int i=0;i<k;i++){
            //模拟数组右移的过程
            int t=nums[nums.length-1];
            for(int j=nums.length-1;j>0;j--){
                nums[j]=nums[j-1];
            }
            nums[0]=t;
        }
    }*/
    //翻转数组：多次翻转--方法4
    /*public void rotate(int[] nums, int k) {
        k= k % nums.length;
        if(k!=0){
            reverse(nums,0,nums.length-1);
            reverse(nums,k,nums.length-1);
            reverse(nums,0,k-1);
        }  
    }
    public void reverse(int[] nums, int start, int end){
        while(start<=end){
            int tmp=nums[start];
            nums[start]=nums[end];
            nums[end]=tmp;
            start++;
            end--;
        }
    }*/
    //方法五：环形数组
    public void rotate(int[] nums, int k) {
        k= k % nums.length;//对k求余
        if(k!=0){
            int n=nums.length;
            boolean[] visited=new boolean[n];//记录是否访问过
            int tmp=nums[0];//记录下一个要移动的元素值
            for(int i=0,j=0;i<n;i++){
                if(visited[j]==true){//已经移动过，则右移
                    j++;
                    tmp=nums[j];//更新下一个要移动的元素
                    i--;//保证移动次数不变（指针移动不算次数）
                    continue;
                }
                int temp=nums[(j+k)%n];//暂时记录下一次循环的元素
                nums[(j+k)%n]=tmp;//进行此次移动
                tmp=temp;//更新记录值
                visited[j]=true;//记录已移动过
                j=(j+k)%n;//寻找下一个要移动元素的下标
            }
        } 
    }

}