数组 / Q189: 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

比如，输入[1,2,3,4,5,6]，k=2，那么输出就是[5,6,1,2,3,4]。可以很清楚地看到数组有两个部分，分别是下标[0,n-k-1]和[n-k,n-1]（n为数组长度），即以n-k-1为划分界线。

公认的套路是使用翻转，我写的代码如下：

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

    public void reverse(int start, int end, int[] array) {
        int i = start;
        int j = end;
        while(i<=j ){
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
            i++;
            j--;
        }
    }

一个算法理论上要能处理所有情形，才是一个合格的算法。以上的代码是无法通过Leetcode的测试的，因为完全没有考虑违规值。比如输入nums为空，或者k>n的情况。因此，需要加上以下代码：

 if (nums==null || n <= 0 || k <= 0)
            return;
 // k maybe larger than n
 k = k % n;

此外，reverse方法也是一个很通用的方法。使用两个指针，一个在头，一个在尾，进行交换。

 public void reverse(int start, int end, int[] array) {
        int i = start;
        int j = end;
        while(i<=j ){
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
            i++;
            j--;
        }

另，我觉得rotate方法里三次调用reverse方法的写法，非常美丽。是代码本身的美丽。

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