每日一题---OJ题: 旋转数组
片头
嗨! 小伙伴们,咱们又见面啦,今天我们一起来学习一道OJ题---旋转数组
emmm,看上去好像没有那么难,我们一起来分析分析
比如: 数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置
第一次轮转:将最后一个元素"7"放在第一个位置,后面的元素依次往后移动,变成 7, 1, 2, 3, 4, 5, 6
第二次轮转:将最后一个元素"6"放在第一个位置,后面的元素依次往后移动,变成 6, 7, 1, 2, 3, 4, 5
第三次轮转:将最后一个元素"5"放在第一个位置,后面的元素依次往后移动,变成 5, 6, 7, 1, 2, 3, 4
针对这道题,我们提供3种思路:
思路1: 右旋k次, 每次挪动旋转一位
定义一个变量temp,用来保存最后一个元素,将最后一个元素放到第一个位置,同时将后面的元素依次往右移动
代码如下:
void Reverse(int arr[], int time, int size) {
time = time % size; //求具体的旋转次数
for (int i = 0; i < time; i++) {
//将最后一个元素保存在temp变量中
int temp = arr[size - 1];
for (int j = size-2; j >=0 ; j--) {
//从下标为size-2的元素开始,一直到下标为0的元素,依次往后移动一位
arr[j + 1] = arr[j];
}
//将最后一个元素放入第一个位置(还原)
arr[0] = temp;
}
}
int main() {
int time = 3;
int arr[] = { 1,2,3,4,5,6,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
Reverse(arr, time,sz);
for (int i = 0; i < sz; i++) {
printf("%d ", arr[i]);
}
return 0;
}运行结果为:
5 6 7 1 2 3 4
But,当我们把代码放到leetcode上面显示不通过
哈哈哈哈,说明这道OJ题限制了时间复杂度,我们这种思路的时间复杂度为 O(n^2) ,题目不通过
那我们就换一种思路呗!
思路2: 我们把数组分成3个部分逆置,假设数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置
第一个部分: 前n-k个逆置,这里的 n 为 7, k 为 3,也就是前4个逆置,变成 4, 3, 2, 1, 5, 6, 7
第二个部分: 后k个逆置, 这里的 k 为 3,也就是后3个逆置, 变成 4, 3, 2, 1, 7, 6, 5
第三个部分: 整体逆置,变成了 5, 6, 7, 1, 2, 3, 4
代码如下:
void Reverse1(int arr[], int start, int end) {
int left = start; //将start赋给left变量
int right = end; //将end赋给right变量
while (left < right)
{
//当left小于right的时候,进入循环
//用临时变量temp实现逆置(左右元素交换)
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++; //每交换完一次,left向右移动
right--; //每交换完一次,right向左移动,直到两个变量相遇
}
}
int main() {
int time = 3;
int arr[] = { 1,2,3,4,5,6,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
Reverse1(arr, 0, sz - time - 1); //前n-k个逆置
Reverse1(arr, sz - time, sz - 1); //后k个逆置
Reverse1(arr, 0, sz - 1); //整体逆置
for (int i = 0; i < sz; i++) {
printf("%d ", arr[i]);
}
return 0;
}运行结果为:
5 6 7 1 2 3 4
同时,我们将代码放到leetcode当中,显示通过
嗯,这种方法好是好,但是好像我如果第一次做这种题,肯定想不出来,那有木有第3种思路呢?
有的! 接下来我就来介绍第三种思路
思路3: 我们可以定义一个新的数组,用memcpy函数将原数组的内容拷贝到新数组中去,拷贝元素的同时,也就完成了逆置
代码如下:
void Reverse2(int arr[], int size, int time) {
time = time % size; //求出最终旋转次数
int temp[20] = { 0 }; //定义一个临时数组temp,初始化数组为0
//将原数组的后time个数拷贝到临时数组temp的前面位置中
memcpy(temp, arr + size - time, sizeof(int) * time);
//将原数组的前size-time个数拷贝到临时数组temp的后面位置中
memcpy(temp + time, arr, sizeof(int) * (size - time));
//将临时数组temp的所有元素拷贝回原数组
memcpy(arr, temp, sizeof(int) * size);
}
int main() {
int nums[] = { 1,2,3,4,5,6,7 };
int time = 3;
int size = sizeof(nums) / sizeof(nums[0]);
Reverse2(nums, size, time);
for (int i = 0; i < size; i++) {
printf("%d ", nums[i]);
}
return 0;
}运行结果为:
5 6 7 1 2 3 4
我们把代码提交到leetcode上去,显示通过
片尾
今天我们学习了轮转数组这道OJ题,希望看完这篇文章能对友友们有所帮助 ! ! !
求点赞收藏加关注 ! ! !
谢谢大家 ! ! !
原文地址：https://blog.csdn.net/qq_74336191/article/details/137611011
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！