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

循环移动数组，注意这里k可能会大于n，所以实际上k = k % n

如果不考虑额外空间复杂度那么就是新创建一个数组，然后指针移动k+1位后将值复制到新数组中然后拷贝剩下的部分。 如果要求O(1)空间则需要将数组分为两部分 1, 2, 3, 4 | 5, 6, 7 分别逆转两部分求得 4, 3, 2, 1 | 7, 6, 5 然后再逆转整个数组可得最终结果 5, 6, 7, 1, 2, 3, 4

public void rotate(int[] nums, int k) {
    int n  = nums.length;
    k = k % n;
    reverse(nums, 0, n - k - 1);
    reverse(nums, n - k, n - 1);
    reverse(nums, 0, n - 1);
}

private void reverse(int[] nums, int left, int right) {
    while(left < right) {
        int tmp = nums[left];
        nums[left++] = nums[right];
        nums[right--] = tmp;
    }
}