用Java将数组中的元素向右移动_给定一个数组,将数组中的元素向右

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]

解答：

首先分析题目：例子中的元素和leetcode中的程序都指定元素为整型，况且其他数据类型也是一样的，所以用整型数组作答。k为非负数，就有可能是0，也可能比数组的长度大，也就是说k=203131234，而数组只有3个元素，这里就需要取模运算；数组的长度没有限制，就说明可能是0个元素，也可能是10亿个元素（占满4G内存）。首先看能比较直观想到的算法：

解法1：使用另外一个数组，直接把元素移动到指定位置

    //时间复杂度O(n) n为数组长度
    //空间复杂度O(n) n为数组长度
    public void rotate(int[] nums, int k) {
       
        if(k==0){return;}
        
        int n = k%nums.length;
        
        int[] tmp = new int[n];
        
        for(int i=0;i<n;i++){
            tmp[i]=nums[nums.length-n+i];
        }
        
        for(int i=nums.length-1;i>=n;i--){
            nums[i]=nums[i-n];
        }
        
        for(int i = 0;i<n;i++){
            nums[i]=tmp[i];
        }
      
    }

分析：首先排除特殊情况k=0，并将k和数组长度取模运算，用new重新创建一个数组，这里可以用.clone()方法简化，下面的循环移动数组元素的逻辑，只把移动元素时会被覆盖的元素备份出来，然后在移动完元素后，把备份的元素移动回去。拷贝数组元素的操作可以从for循环简化为使用System.arraycopy 这样更快。

解法1简化：

    //时间复杂度O(n) n为数组长度
    //空间复杂度O(n) n为数组长度    
    public void rotate(int[] nums, int k) {
        k=k%nums.length;
        int[] tmp=nums.clone();
        System.arraycopy(tmp,tmp.length-k,nums,0,k);
        System.arraycopy(tmp,0,nums,k,tmp.length-k);
    }

解法2：每次把所有元素向右移动1个位置，移动k轮，使用额外的k个变量的空间，这种叫冒泡旋转

    //时间复杂度O(k*n)  k为右移的实际次数(k%n) n为数组长度
    //空间复杂度O(1)
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if (k % len == 0) return;
        k = k % len;
        for (int i = 0; i < k; i++) {
            int temp = nums[len-1];
            System.arraycopy(nums, 0, nums, 1, len-1);
            nums[0] = temp;
        }
    }

 

解法3：不使用额外空间，三次反转代替移动

    //时间复杂度O(n)
    //空间复杂度O(1)
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    
    //反转数组
    public void reverse(int[] nums, int left, int right){
        while (left < right) {
            nums[left] = nums[right] ^ nums[left];
            nums[right] = nums[right] ^ nums[left];
            nums[left] = nums[right] ^ nums[left];
            left++;
            right--;
        }
    }

分析：

reverse方法是把数组中从left到right位置的元素颠倒过来，那为什么颠倒过来就相当于右移呢，直观解释，请看下面一幅图：

reverse方法中之所以用异或，这只是三种交换两个数的方式中，最快的一种。

reverse算法是运行时间最快（不使用额外空间），运行效率更稳定，代码更简洁的一种方式。

其实还有一种杂凑算法（juggling algorithm），其中用到了最小公约数，因为过于复杂，不在这里列出，有兴趣的同学可以看下面的参考2。

知识点：

1.System.arraycopy()方法复制数组元素的速度比用for循环快，见《Java中数组复制的几种方法》

2.数组名字.clone()可以克隆数组，不再需要用new

3.交换两个整数，可以不用临时变量，用异或效率最高

参考：

1.《Program for array rotation》 https://www.geeksforgeeks.org/array-rotation/

2.《编程珠玑笔记：数组循环左移》https://www.cnblogs.com/longcpp/p/4029664.html

3.《Java 交换两个数的三种方法》https://blog.csdn.net/yancewong/article/details/80550720