宁波市建设工程监理协会网站青岛网站建设 新视点
片头
嗨! 小伙伴们,咱们又见面啦,今天我们一起来学习一道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题,希望看完这篇文章能对友友们有所帮助 ! ! !
求点赞收藏加关注 ! ! !
谢谢大家 ! ! !
