2015年10月24日星期六

Leetcode 189 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.
Solution 1: O(k) space
 public class Solution {  
   public void rotate(int[] nums, int k) {  
     int n=nums.length;  
     k%=n;  
     int[] t=new int[k];  
     for (int i=n-1; i>=0; i--) {  
       if (i+k>=n) t[i+k-n]=nums[i];  
       else nums[i+k]=nums[i];  
     }  
     for (int i=0; i<k; i++) nums[i]=t[i];  
   }  
 }  

Solution 2: O(n), O(1) use 3 reverse.
 public class Solution {  
   public void rotate(int[] nums, int k) {  
     int n=nums.length;  
     k%=n;  
     reverse(nums,n-k,n-1);  
     reverse(nums,0,n-k-1);  
     reverse(nums,0,n-1);  
   }  
   private void reverse(int[] nums, int lo, int hi) {  
     while (lo<hi) {  
       int temp=nums[lo];  
       nums[lo++]=nums[hi];  
       nums[hi--]=temp;  
     }  
   }  
 }  


没有评论:

发表评论