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.
[show hint]
Hint:
Could you do it in-place with O(1) extra space?
//先将5以前的数据翻转得到的数组是[4,3,2,1,5,6,7]
//再将5及以后的数据翻转得到的数组是[4,3,2,1,7,6,5]
//再将整个数组翻转即得到[5,6,7,1,2,3,4]. (即为所求)
// while(i < j && i >= 0) 如果没有了等于0则会变得2个元素的时候不通过
public class Solution { public void rotate(int[] nums, int k) { int len = nums.length; k = k % len; if(nums.length == 1){ return; } if(k == 0){ return; } reverse(nums, 0, len - 1 - k); reverse(nums, len - k, len - 1); reverse(nums, 0, len - 1); } public void reverse(int[] nums, int i, int j){ while(i < j && i >= 0){ int temp = 0; temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; i++; j--; } } }