2016年10月12日星期三

189. Rotate Array QuestionEditorial Solution

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
两种方法,第二种比较巧妙

   public void rotate(int[] nums, int k) {  
     int n = nums.length;  
     if(n == 0||k==0) return;  
     k %= n;  
     int c = 0,i=0;  
     while(c < n){  
       int j = i + k;  
       if(j>n)   
         break;  
       int num = nums[i];  
       while(j != i && j < n){  
         int tmp = nums[j];  
         nums[j] = num;  
         num = tmp;  
         j += k;  
         c++;  
         if(j>n) j%=n;  
       }  
       nums[i] = num;  
       c++;  
       i++;  
     }  
   }  

三步反转法 BA=(A1B1)1
public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

没有评论:

发表评论