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.

Naive Way: 要想三种方法。
1.最简单的一种就是用一个新数组去装载新的数组然后再复制回去。这种方法需要O(n) space，算法复杂度是O(n)。实际做的时候还发现k会出现比n大的情况。

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     int temp[] = new int[nums.length];  
     for(int i = 0;i < nums.length;i++)  
       temp[i] = i < k? nums[nums.length-k+i]:nums[i-k];  
     for(int i = 0;i < nums.length;i++)  
       nums[i] = temp[i];  
   }  
 }  

在原来的方法上想，优化一下可以使空间可以降到O(min(k,n-k))

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     if(nums.length-k > k){  
       int temp[] = new int[k];  
       for(int i = 0;i < k;i++)  
         temp[i] = nums[nums.length-k+i];  
       for(int i = nums.length-1;i >= k;i--)  
         nums[i] = nums[i-k];  
       for(int i = 0;i < k;i++)  
         nums[i] = temp[i];  
     }else{  
       int temp[] = new int[nums.length-k];  
       for(int i = 0;i < temp.length;i++)  
         temp[i] = nums[i];  
       for(int i = 0;i < k;i++)  
         nums[i] = nums[i+nums.length-k];  
       for(int i = 0;i < nums.length-k;i++)  
         nums[i+k] = temp[i];  
     }  
   }  
 }  

2. 可以模仿rotate linked list 的插值法，不过在数组上插值，每一次就要移动 n 位了，这样就得到一个算法复杂度为O(nk), space O(1) 的方法。但是这样会超时。

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     for(int i = 0;i < k;i++){  
       int temp = nums[nums.length-k+i];  
       for(int j = nums.length-k+i;j >= i+1;j--)  
         nums[j] = nums[j-1];  
       nums[i] = temp;  
     }  
   }  
 }  

3.可不可以仅通过swap来实现O(1)。 好像可以通过recursive的greedy算法实现。
于是写了这个O(1) space的算法，弄了好久。核心思想是在不产生overlap的情况下，尽可能多的交换， 然后剩下的没有进行交换的则建立新的分割，由下一个recursive的函数进行交换。

算法复杂度是O(n) （每个数最多被交换两次）

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     rotate(nums,0,nums.length-k-1);  
   }  
   /*  
   * begin is where the sequence to be processed starts  
   * end is the cut where separates the two slices of the array  
   * nums = [<processed>,<       to be processed         >]  
   *                  |                        |   
   *                  <begin, end>, <end+1, nums.length-1>  
   * Afterwards:        <processed >, <  to be processed    >   
   */  
   private void rotate(int[] nums, int begin, int end){  
     // base case  
     if(end == nums.length-1) return;  
     // recursive  
     int k = Math.min(end-begin+1, nums.length-1-end);  
     for(int i = 0; i < k;i++)  
       swap(nums, begin+i, end+1+i);  
     if(k==end-begin+1)  
       rotate(nums, begin+k, end+k);  
     else  
       rotate(nums, begin+k, nums.length-k-1);  
   }  
   private void swap(int[] nums, int index1, int index2){  
     int temp = nums[index1];  
     nums[index1] = nums[index2];  
     nums[index2] = temp;  
   }  
 }  

Improved Way:在Discuss里看到了两个很好的方法。

第一个是
mjsaber的，不得不说他这个做法实在太聪明了。先把整个数组头尾互换，此时要交换的两部分已经处于各自半区了，但是顺序是反的，然后在内部翻转。这个方法是主流的方法。

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     if (nums == null || nums.length == 0) {  
       return;  
     }  
     k = k % nums.length;  
     reverse(nums, 0, nums.length-k-1);  
     reverse(nums, nums.length-k, nums.length-1);  
     reverse(nums, 0, nums.length-1);  
   }  
   private void reverse(int[] num, int left, int right) {  
     while (left < right) {  
       int t = num[left];  
       num[left] = num[right];  
       num[right] = t;  
       left++;  
       right--;  
     }  
   }  
 }  

第二个是 xcv58的，采用从后往前换，每次换好一个找当前这个要换的位置。

 public void rotate(int nums[], int n, int k) {  
   for (int i = 0, j = k % n, previous = nums[i], anchor = i, count = n; count > 0; count--, j = (i + k) % n) {  
     int tmp = nums[j];  
     nums[j] = previous;  
     previous = tmp;  
     if ((i = j) == anchor) {  
       i = (i + 1) % n;  
       previous = nums[i];  
       anchor = i;  
     }  
   }  
 }