Reverse Array

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

双数组

复杂度

时间 O(N) 空间 O(N)

思路

建立一个新数组，将位移过的数字放在新的数组中。

反转法

复杂度

时间 O(N) 空间 O(1)

思路

通过三次反转，我们可以很巧妙的实现旋转数组。首先我们将整个数组反转，然后将前k个数字反转，然后再将后面剩下的数字反转，就得到目标数组了。

注意

• 反转数组最简单的方法是交换元素，而交换元素有至少三种方法（临时变量，相加相减，异或）

• k可能大于数组长度，旋转不止一次，所以我们要先对k取余

代码

public class Solution {    public void rotate(int[] nums, int k) {        k = k % nums.length;        reverse(nums, 0, nums.length-1);        reverse(nums, 0, k-1);        reverse(nums, k, nums.length-1);    }        private void reverse(int[] nums, int i, int j){        while(i<j){swap(nums, i, j);i++;j--;        }    }        private void swap(int[] nums, int i, int j){        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }}