Leetcode 数组问题3：旋转数组

问题描述：

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 ：

输入a数组: [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]

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 o(1) 的原地算法。

问题分析：

将数组中的元素向右移动，并要求空间复杂度为o(1)，每移动一次，数组的最后一个元素移动到首位，其余元素均向后移动一位，

以上面的a数组为例，可以将a[6]=7先拿出来，不被向后移动的其他数组元素的值覆盖掉，然后将其余元素向后移动一位，数组变为[a[0],1,2,3,4,5,6],再把

a[6]的值赋给a[0],这样就完成了一次数组的移动,循环上述过程即可。这种方法时间复杂度为o(kn),比较耗时

翻转算法：先将数组整个翻转一遍，将后面的元素移动到了前面，但是这时的元素顺序并不满足要求，需要将索引为[0,k-1]，和 [k,n-1]的元素翻转回来

时间复杂度为o(n)

 以上面的a数组为例：

     [1,2,3,4,5,6,7] --翻转索引为[0,n-1]之间的元素--> [7,6,5,4,3,2,1] 
                     --翻转索引为[0,k-1]之间的元素--> [5,6,7,4,3,2,1] 
                     --翻转索引为[k,n-1]之间的元素--> [5,6,7,1,2,3,4]

java实现：

class solution {
    public void rotate(int[] nums, int k) {
        int len=nums.length;
        k=k%len;//移动的长度只需要对原数组长度取余即可，当k=len时，数组不变
        int temp=0;
        if(k==0){}
        else{
            for(int j=0;j<k;j++){              
               temp=nums[len-1];//先将数组最后一个元素的值赋给temp 
             for(int i=len-2;i>=0;i--){
                nums[i+1]=nums[i];//剩余数组元素均向右移动一位
            }
                nums[0]=temp;//数组最后一个元素移动到第一个元素的位置
            }
            
        }
    }
}

 

class solution {
//翻转算法
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k%n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }


    private void reverse(int[] nums, int i, int j) {
        while (i< j) {
            int temp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = temp;
        }
    }
}