189.轮转数组
数组翻转:
当我们将数组的元素向右移动k次后,尾部k mod n个元素会移动至数组 头部,其余元素向后移动k mod n个位置
该方法为数组的翻转:我们可以先将所有元素翻转,这样尾部k mod n个元素就被移至数组头部,然后我们再翻转[0, k mod n -1]区间的元素和[k mod n,n-1]区间的元素即能得到最后的答案
以n=7,k=3为例进行展示:
操作 | 结果 |
---|---|
原始数组 | 1 2 3 4 5 6 7 |
翻转所有元素 | 7 6 5 4 3 2 1 |
翻转[0,k mod n-1]区间的元素 | 5 6 7 4 3 2 1 |
翻转[k mod n,n-1]区间的元素 | 5 6 7 1 2 3 4 |
class Solution {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 tmp = nums[start];nums[start] = nums[end];nums[end] = tmp;start += 1;end -= 1; }}
}