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

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

[show hint]

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

Related problem: Reverse Words in a String II

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

---

题目标签：Array
　　题目给了我们一个数组 和 k。 让我们 旋转数组 k 次。

这里有一个很巧妙的方法：
　　利用数组的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 一下就会得到答案

关键词：Array
关键点：利用k把数组分两半；reverse左右两边数组；reverse总数组

代码实现

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--;
        }
    }
    
}