问题描述：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 ：
输入A数组:[1,2,3,4,5,6,7]和 k = 3 输出:[5,6,7,1,2,3,4]解释: 向右旋转 1 步:[7,1,2,3,4,5,6]向右旋转 2 步:[6,7,1,2,3,4,5]向右旋转 3 步:[5,6,7,1,2,3,4]尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的原地算法。
问题分析：
将数组中的元素向右移动，并要求空间复杂度为O(1)，每移动一次，数组的最后一个元素移动到首位，其余元素均向后移动一位，
以上面的A数组为例，可以将A[6]=7先拿出来，不被向后移动的其他数组元素的值覆盖掉，然后将其余元素向后移动一位，数组变为[A[0],1,2,3,4,5,6],再把
A[6]的值赋给A[0],这样就完成了一次数组的移动,循环上述过程即可。这种方法时间复杂度为O(KN),比较耗时
翻转算法：先将数组整个翻转一遍，将后面的元素移动到了前面，但是这时的元素顺序并不满足要求，需要将索引为[0,k-1]，和 [k,n-1]的元素翻转回来
时间复杂度为O(n)
以上面的A数组为例：
[1,2,3,4,5,6,7] --翻转索引为[0,n-1]之间的元素--> [7,6,5,4,3,2,1]
--翻转索引为[0,k-1]之间的元素--> [5,6,7,4,3,2,1]
--翻转索引为[k,n-1]之间的元素--> [5,6,7,1,2,3,4]JAVA实现：
class Solution { public void rotate(int[] nums, int k) { int len=nums.length; k=k%len;//移动的长度只需要对原数组长度取余即可，当k=len时，数组不变 int temp=0; if(k==0){} else{ for(int j=0;j<k;j++){ temp=nums[len-1];//先将数组最后一个元素的值赋给temp for(int i=len-2;i>=0;i--){ nums[i+1]=nums[i];//剩余数组元素均向右移动一位 } nums[0]=temp;//数组最后一个元素移动到第一个元素的位置 } } } }
class Solution {
//翻转算法 public void rotate(int[] nums, int k) { int n = nums.length; k = k%n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } private void reverse(int[] nums, int i, int j) { while (i< j) { int temp = nums[i]; nums[i++] = nums[j]; nums[j--] = temp; } } }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
