标题描绘
给定一个数组,将数组中的元素向右移动 k 个方位,其间 k 对错负数。
进阶:
尽可能想出更多的处理方案,至少有三种不同的办法能够处理这个问题。
你能够运用空间复杂度为 O(1) 的 原地 算法处理这个问题吗?
来历:力扣(LeetCode)
示例 1:
输入: nums = [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]
示例 2:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
阐明:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步数组指针: [3,99,-1,-100]数组去重
提示:
- 1 <= nums.length <= 2 * 104
- -231 <leetcode每日一题= nums[i] <= 231 – 1
- 0 <= k <= 105
标题剖析
对这道标题,我考虑了好久,想出了下面两种做法。
第leetcode中文官网一种:凭仗一个新的数组
-
首要总结出元素向移动
k
个方位后的下标规矩。这种数组元素旋转的进程,很像循环行列元素进行移动的特征。下标i
的向移动k
个方位后的下标状况为i = (i + k)%numsSize
-
声明算法一个新的数组(和原数组leetcode官网相同的长度),然后依次填入转化方位后的值。以原数组旋元素转后的下标作为新数组元素的下标,一起赋值给新数组的元素,全部元素赋值结束后。反过来用新数组给原数组的元素一一对应赋值。
-
假定数组的长度
numsSize
和算法的特征移动方位数成倍数联系(即k % numsSize == 0
),那么无leetcode高频100题需移动。
第二种:选用链表遍历的思维
-
首要总结出元素向移动
k
个方位后的下标规矩。这种数组元素旋转的进程,很像循环行列元素进行移动的特征。下标i
的向移动k
个方位后的下标状况为i = (i + k) % numsSize
-
选用相似链表遍历元素的思维,对数组元素进行旋转。但这样的做法会有两种状况出LeetCode现。
- 经过下标的移动可数组排序以遍历到全部元素,举个比如
给出上述数组,算法规划与剖析向右移动 3 个元素。元素移动示意图
详细关于完结这个代码:
// 批改完全部元素间断 while(count>0) { // 选用了两个数进行数值交流的办法 nums[(i+k)%numsSize] = nu数组去重ms[(i+k)%numsSize] + item; item = nums[(i+k)%numsSize] - item; nums[(i+k)%numsSize] = nums[(i+k)%numsSleetcode刷题攻略ize] - item; // i 用来操控移动 i = (i+k)%numsSize; count--; }
为了防止赋值掩盖的问题,界说了变量
i算法规划与剖析tem
来记住旋转赋值前该元素的中值,item
的初始值为nums[0]
。- 经过下标的移动求模能够遍历到一部分元素,举个比如
如图数组,向右移动 6 个元素。元素移动示意图
你可看到在这种数组c语言状况中,并没有遍历到全部的元素,该怎样办呢?其实在这种状况下有一个规矩能够让咱们遍历算法剖析的意图是到全部元素。在这种状况下,原数组会被分割成几个长度相同首尾相连的链表(能够把上面元素的移动了解这种首尾相连链表的遍历),且链表之间的元素不会有交叉重复。咱们只需知道单个链表leetcode是啥的长度
length
即可。一贯从以元素下标i = 0
链表初步旋数组和链表的差异转,到元素下标i=n-1 (n为原数组分割成链表的个数)
结束。 至于上述length,n
该怎样供认,将会在算法第三点数组词阐明。 -
怎样差异怎样
nums
和k
对应上面的两种状况呢?我的做法是经过记算法剖析的意图是载数组指针数组移动的个数,来供认对应上leetcode中文官网述哪种状况。代码如下:
// j 用来记住初始元素下标,i用来进行下标移动leetcode刷多少题找到工作,count用来记载被遍历的元素个数 int j=0,cou算法规划与剖析nt=0,i=0; do { i = (i+k)%numsSize; count++; // 当从数组初始化头移动原方位时刻断数组去重的5种方法 }while(j!=i);
假定
count =算法导论= numsSize
,那么归于能够经过一个元素遍历到全部元素的状况。否则归于第二种状况。第二种状况剖析:咱们要供认的链表长度
length
就等于上文的数组排序count
,一起连败哦的个数可leetcode和牛客网差异以leetcode和牛客网差异经过n = numsSize/count
供认。在此附上这种状况的完结代码:// 外层循环操控链表的初步方位,内层循环操控旋转 for(i=0;i<numsSize/count;i++) { // j完结下标移动,item记载旋转赋值前元素的值 le算法规划与剖析n算法的特征gth记载批改元素的个数 j = i,item = nums[i],length=0; do { nums[(j+k)%nums算法的有穷性是指Size] = nums[(j+k)%numsSize] + item; item = nums[(j+k)%numsSize] - item; nums[(j+k)%numsSize] = nums[(j+k)%numsSize] - item; j = (j+k)%numsSize; length++; }while(length<count); }
-
假定数组的长度
numsSize
和移动方位数成倍数联系(即k % numsSize == 0
),那么无需移动。
AC代码
第一种:凭仗一个新的数组 时刻复杂度 O(n),空间复杂度 O(n)
v算法的特征oid rotate(int* nums, int numsSize, int k){
int number[numsSize],j;
for(int数组去重的5种方法 i=0;i<算法numsSize;i++算法的特征)
{
j = (i+k)%numsSize;
number[j] = nums[i];
}
for(j算法剖析的意图是=0;数组去重的5种方法j<numsSize;j++)
{
nums[j] = number[j];
}
}
第二种:选用链表遍历的思维 时刻复杂度 O(n),空间复杂度 O(1)
voidleetcode刷题攻略 rotate(int* nums, int numsSize, int k){
if(k!=0)
{
intleetcode怎样刷题 j=0,count=0,i=0,item;
do
{
i = (i+k算法剖析的意图是)%numsSize;
count++;
}
while(j!=i);
if(count==numsSize)
{
item = nums[0];
while(count>数组排序0)
{
nums[(i+k)%numsSize] = nums[(i+k)%numsSize] + item;
item = nums[(i+k)%numsSize] - item;
nums[(i+k)%numsSize数组去重] = nums[(i+k)%numsSize] - item;
i = (i+k)%numsSize;
c数组去重的5种方法ount--;
}
}
else
{
int length;
for(i=0;i&l算法的时刻复杂度是指什么t;numsSize/cou算法剖析的意图是nt;i++)
{
j = i,item = nums[i],length=0;
do
{
nums[(j+k)%numsSize] = nums[(j+k)%numsSize] + item;
item = nums[(j+k)%numsSize] - item;
nums[(j+k)%numsSize] = nums[(j+k)%numsSizleetcode怎样刷题e] - item;
j = (j+k)%numsSize;
length++;
}while(length<count)leetcode怎样刷题;
}
}
}
}
至于第三种办法,作者才能有限未能想出,不过能够参看LeetCode官方回答
终究
这是我的 L数组和链表的差异eetCode 刷题打卡的 No数组词.6
篇,还有后续华章等候更新数组初始化。作者在此央求看完点个赞吧,数组c语言码字不易
本文正在参与「 3 月闯关活动」,点击检查算法的时刻复杂度是指什么活动LeetCode概略。