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
两种方法,第二种比较巧妙
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=(A−1B−1)−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--;
}
}
没有评论:
发表评论