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

思路1：利用另一个数组b，把原数组的元素分两步存放到数组b，之后再把数组b的元素复制到原数组。此种方法Space is O(n) and time is O(n).

JAVA代码如下：

public void rotate(int[] nums, int k) {
  if(k > nums.length) 
    k=k%nums.length;
  int[] result = new int[nums.length];
  for(int i=0; i < k; i++){
    result[i] = nums[nums.length-k+i];
  }
  int j=0;
  for(int i=k; i<nums.length; i++){
    result[i] = nums[j];
    j++;
  }
  System.arraycopy( result, 0, nums, 0, nums.length );
}

思路2：利用冒泡排序的思想，进行冒泡旋转(注意，此种方法 time is O(n*k)，在leetcode上是Time Limit Exceeded)。

JAVA代码如下：

public void rotate(int[] nums, int k) {
        if (nums == null || k < 0) {
            throw new IllegalArgumentException("Illegal argument!");
        }
        for (int i = 0; i < k; i++) {
            for (int j = nums.length - 1; j > 0; j--) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
    }

思路3：根据规律，分三步旋转，此种方法最优，O(1) space and O(n) time。

JAVA代码：

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return;
        }
        k = k % n;     // remove multiple
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
    public void reverse(int[] nums, int m, int n) {
        while (m < n) {
            int tmp = nums[n];
            nums[n] = nums[m];
            nums[m] = tmp;
            m ++;
            n --;
        }
    }