题目
将包含 n 个元素的数组向右旋转 k 步。
例如,如果 n = 7 , k = 3,给定数组 [1,2,3,4,5,6,7]
,向右旋转后的结果为 [5,6,7,1,2,3,4]
。
注意:
尽可能找到更多的解决方案,这里最少有三种不同的方法解决这个问题。
提示:
要求空间复杂度为 O(1)
关联的问题: 反转字符串中的单词 II
思路:
假设原数组序列为abcd1234,要求变换成的数组序列为1234abcd,即循环右移了4位。比较之后,不难看出,其中有两段的顺序是不变的:1234和abcd,可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成:
逆序排列abcd:abcd1234 → dcba1234;
逆序排列1234:dcba1234 → dcba4321;
全部逆序:dcba4321 → 1234abcd。
时间复杂度为O(n)
public void rotate(int[] nums, int k) {
int n = nums.length;
//旋转后下标值为0:(index+k)%n=0,则index=n-k
int index = (n-k)%n;
if(index<0){
index=index+n;
}
convert(nums,index,nums.length-1);
convert(nums,0,index-1);
convert(nums,0,nums.length-1);
}
private void convert(int[] nums,int start,int end){
int m=start;
int n=end;
int temp;
while(m<n){
temp = nums[m];
nums[m]=nums[n];
nums[n]=temp;
m++;
n--;
}
}
网友评论