宁波网站建设计,杭州置地电商基地网站建设,网页制作培训好学吗,旅游门户网站系统对于轮转数组这个题#xff0c;文章一共提供三种思路#xff0c;对于每种思路均提供其对应代码的时间、空间复杂度。 目录
1. 创建变量来保存最后一个数#xff0c;并将其余数组向前挪动一位 #xff1a;
1.1 原理解析#xff1a;
1.2 代码实现#xff1a; 2.创建一个…对于轮转数组这个题文章一共提供三种思路对于每种思路均提供其对应代码的时间、空间复杂度。 目录
1. 创建变量来保存最后一个数并将其余数组向前挪动一位
1.1 原理解析
1.2 代码实现 2.创建一个数组用于存放需要旋转的元素并放到相应位置
2.1 原理解析
2.2 代码实现
3. 先左部分右旋再右部分右旋最后整体逆序(三段逆序法
3.1 原理解析 3.2 代码实现 题目要求如图所示 1. 创建变量来保存最后一个数并将其余数组向前挪动一位
注第一种思路虽然可以解决问题但是代码的时间复杂度为空间复杂度为时间复杂度不符合LeetCode的提交标准所以第一种思路仅供参考与扩展。
1.1 原理解析 假设一个数组为
nums[7] {1,2,3,4,5,6,7};
为了方便表示用下图来代表数组及数组中的元素 第一步先将数组种最后一位元素即7用一个临时变量保存。 第二步将其他剩余元素全部向右移动一位。 第三步 把临时变量保存的7放到数组的首元素的位置。 至此完成一次交换。
1.2 代码实现
用代码表示上述过程即
#includestdio.h
#includeassert.h
void rotata(int* nums,int numsize)
{assert(nums);int tmp nums[numsize - 1];//用临时变量保存数组最后一个元素int i 0;for (i 6 ; i 0; i--){nums[i] nums[i - 1];//将其余元素向右移动一位}nums[0] tmp;//将临时变量保存的元素放在数组首个元素的位置
}
int main()
{int nums[7] { 1,2,3,4,5,6,7 };int sz sizeof(nums) / sizeof(nums[0]);rotata(nums, sz );return 0;
}
打印结果如下 上面的代码只能实现右移一位。对于移动多个元素可以将上面移动一个元素的过程用循环来进行。例如用变量来代表旋转的次数代码为
#includestdio.h
#includeassert.h
void rotata(int* nums,int numsize,int k)
{k k % numsize 1;//防止k过大使k的范围在0-7assert(nums);int j 0;for (j 0; j k; j){int tmp nums[numsize - 1];//用临时变量保存数组最后一个元素int i 0;for (i 6; i 0; i--) //0 1 2 3 4 5 6 // 1 2 3 4 5 6{nums[i] nums[i - 1];//将其余元素向右移动一位}nums[0] tmp;//将临时变量保存的元素放在数组首个元素的位置}}
int main()
{int nums[7] { 1,2,3,4,5,6,7 };int sz sizeof(nums) / sizeof(nums[0]);int k 0;scanf(%d, k);rotata(nums, sz,k );int i 0;return 0;
}
因为数组每旋转7次数组中的元素就回到不旋转的位置所以即使在输入旋转次数为77次时得到的效果也和旋转一次一样
旋转一次效果 旋转两次效果 旋转77次 但是当的值过大时因为每右旋7次就是一个循环所以为了减少编译器的工作量用%,让的取值范围保持在这个区间闭区间 2.创建一个数组用于存放需要旋转的元素并放到相应位置
方法二的时间复杂度为,空间复杂度为
2.1 原理解析
依旧使用上面的图来解释思路
右旋一次 右旋两次: 对于上面的两种情况不难发现其实所谓的右旋可理解为将需要进行右旋的元素看成一个整体让后放到其余元素的前面例如旋转两次时
第一步将元素看作一个整体其余元素看成一个整体。 第二步作为整体的放到剩余元素的前面进行整合 2.2 代码实现
有了解决问题的思路后下面给出具体实现的代码
void rotate(int* nums, int numsSize, int k){int n numsSize;int* tmp (int*)malloc(sizeof(int)*(n));k k%n;memcpy(tmp,numsn-k,sizeof(int)*(k));memcpy(tmpk,nums,sizeof(int)*(n-k));memcpy(nums,tmp,sizeof(int)*(n));free(tmp);} 整体代码的逻辑为 n是数组中元素的个数k是执行右旋的次数。
1.先用malloc开辟一块空间
2.用%来限制的取值范围。
3.先利用memcpy函数将nums数组种起始地址数量为的元素拷贝到tmp这个临时空间种。
4.再利用memcpy函数将nums剩余的元素拷贝到tmp中。
此时tmp已经存储了旋转后的数组。
5.将tmp中的元素赋值到nums中。
执行结果如下 从结果中可以看到方法二是用空间来换取速度的方法。
3. 先左部分右旋再右部分右旋最后整体逆序(三段逆序法
最优解法时间复杂度为空间复杂度因为只创建了一个额外的临时变量为
3.1 原理解析
对于三段逆序法同样使用图片来解释
假设数组名为,数组中的元素个数为,按照LeetCode中7个元素。需要旋转的位数为。下面的代码就拿来解释。
第一步先将左部分元素整体逆序,即把下标从0到(即数组中第一个到第四个元素逆序的元素逆序 第二步将右半部分元素整体逆序即把下标为到(即数组中第五个到第七个元素逆序 第三步整体逆序即对下标从0到的元素逆序 通过LeetCode网站给出的样例发现整体逆序后结果与样例相同 3.2 代码实现 在上面的解释中既然每一步都需要逆序所以为了方便并且减少代码量可以提前封装一个交换函数或者直接使用交换函数这里给出提前封装交换函数的代码
其中变量对应数组,变量对应交换的起始位置变量对于交换的结束位置
void reserve( int*a,int left,int right)
{while(left right){int tmp a[left];a[left] a[right];a[right] tmp;left;right--;}
}
再交换后根据上面对原理的解释对逆序函数进行三次调用并传递相应的参数即可
void rotate(int* nums, int numsSize, int k){int n numsSize;k k%n;reserve(nums,0,n-k-1);reserve(nums,n-k,n-1);reserve(nums,0,n-1);}
整体函数如下
void reserve( int*a,int left,int right)
{while(left right){int tmp a[left];a[left] a[right];a[right] tmp;left;right--;}
}void rotate(int* nums, int numsSize, int k){int n numsSize;k k%n;reserve(nums,0,n-k-1);reserve(nums,n-k,n-1);reserve(nums,0,n-1);}
运行结果如下
