做影视网站需要多大硬盘,餐饮品牌策划设计有限公司,php企业网站开发教程,青岛模板自助建站题目链接#xff1a;189. 轮转数组 - 力扣#xff08;LeetCode#xff09; 思路一
我们可以在进行每次轮转的时候#xff0c;先将数组的最后一个数据的值存储起来#xff0c;接着将数组中前n-1个数据依次向后移#xff0c;最后将存储起来的值赋给数组中的第一个数据。
…题目链接189. 轮转数组 - 力扣LeetCode 思路一
我们可以在进行每次轮转的时候先将数组的最后一个数据的值存储起来接着将数组中前n-1个数据依次向后移最后将存储起来的值赋给数组中的第一个数据。
先将数组中最后的一个元素的值存到变量tmp中如下图 接着将数组中前n-1个数据依次向后移如下图 最后再将tmp中的值赋值给nums[0]如下图 以上图是表示一次轮转的如果还要轮转重复上面的操作。
代码实现
public void rotate(int[] nums, int k) {for(int i0;ik;i){int tmpnums[nums.length-1];//将前n-1个元素向后移for(int jnums.length-1;j0;j--){nums[j]nums[j-1];}nums[0]tmp;}}
当我们提交以上代码时会发现不成功。 思路是对的但是上面代码时间复杂度为O(kn)太复杂了超出了题目的时间限制。
思路二
造成思路一时间复杂度太大的原因是 思路一中有两个循环一个循环是数组右旋的次数另一个循环要将数组中的元素全部遍历一遍这样当右旋次数足够多数组中的元素很多时效率就很低了。
思路二是k次旋转法。
下面以旋转次数为3来讲解也就是k3 先将数组全部旋转一遍如下图 再以下标为0为起始点和下标为(k%nums.length)-1为终点来旋转如下图 最后以下标为(K%数组长度为起始点和以下标为数组长度-1为终点来旋转数组。 这样就完成了数组的3次右旋。
代码实现
public void reverse(int[] nums,int start,int end){while(startend){int tmpnums[start];nums[start]nums[end];nums[end]tmp;start;end--;}}public void rotate(int[] nums, int k) {reverse(nums,0,nums.length-1);reverse(nums,0,(k%nums.length)-1);reverse(nums,k%nums.length,nums.length-1);}
思路三
我们可以创建一个新的数组将原数组中的数据按照数组旋转之后的的位置放置到新数组中对应的位置。最后我们再将新数组复制到原数组中就行了。
有一个公式(ik)%数组的长度) 的值 是 原数组中下标为i的数据 在 新数组中的位置。
其中i为原数组中数据的小标k为旋转次数。
理解公式
假如数组向右旋转k也就是让数组中的数据向右移动k个位置但是如果k大于数组长度就会越界所以我们要%数组的长度。因为如果旋转的次数超过数组的长度也就是旋转k次的效果和k减去数组的长度次的效果是一样的。
代码实现
public void rotate(int[] nums, int k) {int nnums.length;//创建一个新数组jianint[] newNumsnew int[n];//将原数组中的数据放到新数组中for(int i0;in;i){newNums[(ik)%n]nums[i];}//将新数组复制到原数组System.arraycopy(newNums,0,nums,0,n);}
