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.
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;
}
}
}
没有评论:
发表评论