question:

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].

Hint:

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

link:

解法1：

首先会想到的是新开一个数组,按照要求遍历数组nums,并且放到新的数组中去就可以了.

比如:[1,2,3,4,5,6]  n=6 k=2   把数组分成两部分  [1,2,3,4,5,6] 分别放到新的数组中去就可以了

代码实现:

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

 

解法2：

这里有一个很巧妙的方法：

　　　　利用数组的length - k 把数组 分为两半；

　　　　reverse 左边和右边的数组；

　　　　reverse 总数组

举一个例子： 

　　1 2 3 4 5 6 7　　如果k = 3 的话， 会变成 5 6 7 1 2 3 4

　　1 2 3 4 5 6 7　　middle = 7 - 3 = 4，分为左边 4个数字，右边 3个数字

　　4 3 2 1 7 6 5　　分别把左右reverse 一下

　　5 6 7 1 2 3 4　　把总数组reverse 一下就会得到答案

 

 

public class Solution {    public void rotate(int[] nums, int k)     {        if(nums == null || nums.length == 0 || k % nums.length == 0)            return;                int turns = k % nums.length;        int middle = nums.length - turns;                reverse(nums, 0, middle-1); // reverse left part        reverse(nums, middle, nums.length-1); // reverse right part        reverse(nums, 0, nums.length-1); // reverse whole part     }        public void reverse(int[] arr, int s, int e)    {        while(s < e)        {            int temp = arr[s];            arr[s] = arr[e];            arr[e] = temp;                        s++;            e--;        }    }}

 视频讲解：