问题：

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint：

Could you do it in-place with O(1) extra space?

Related problem: 

 

【解析】将数组元素向前移动K步得到的新的数组。

解决：

①首先，数组移动K个位置后下标值为(i + k) % n，新建一个数组，将数值依次移动到对应的位置，这种方法的空间复杂度为O(n).耗时1ms。

public class Solution {

    public void rotate(int[] nums, int k) {         int n = nums.length;         int[] arr = new int[n];         for (int i = 0;i < n ;i ++ ) {             arr[(i + k) % n] = nums[i];         }         for (int i = 0;i < n ;i ++ ) {             nums[i] = arr[i];         }     } }

②类似于冒泡排序，将数组依次向后移动k次即可。时间复杂度为O(n*k)。超时

public class Solution {  

    public static void rotate(int[] nums, int k) {         for (int i = 0;i < k; i ++) {             int tmp = nums[nums.length - 1];             for (int i = nums.length - 1;i > 0 ;i -- ) {                 nums[i] = nums[i - 1];             }             nums[0] = tmp;         }     } }   ③可以通过三次反转数组实现。第一次反转整个数组，第二次反转前K个数组，第三次反转剩余的数组。这种方法不需要额外的空间，空间复杂度为O(1)。耗时2ms。

例如：

一维数组[1,2,3,4,5,6,7],k=3

第一次反转：7,6,5,4,3,2,1

第二次反转：5,6,7,4,3,2,1

第三次反转：5,6,7,1,2,3,4 ----- 最终结果

public class Solution {  

    public void rotate(int[] nums, int k) {           k %= nums.length;//k值超过数组长度时           reverse(nums,  0, nums.length-1);//翻转整个数组           reverse(nums, 0, k-1);//翻转前k个数           reverse(nums, k, nums.length-1);//翻转剩下的数       }       public void reverse(int[] nums, int start, int end) {           while (start < end) {               int temp = nums[start];               nums[start] = nums[end];               nums[end] = temp;               start++;               end--;           }       }   }   ④同理，进行三次翻转。

以n - k为界，分别对数组的左右两边执行一次逆置；然后对整个数组执行逆置。

reverse(nums, 0, n - k - 1)reverse(nums, n - k, n - 1)reverse(nums, 0, n - 1)