数据结构-轮转函数算法题今天练习一道算法题该题地址一、思路最简单的代码#includestdio.h //思路定义一个数组。 //这个数组的最后一个元素单独存下前面的元素依次向后移动一位最后将最后一个元素在移动到第一位。 // 把这个过程重复到想要进行的轮数 int main() { int arr[7] { 1,2,3,4,5,6,7 }; int n 3; // 定义轮数以三为例。即把数组的所有元素都向右移动三次 int arrSize sizeof(arr) / sizeof(arr[0]); //计算数组的大小 while (n--) { //确保轮转的次数是3 { int temp arr[arrSize - 1]; for (int i arrSize - 1; i 0; i--) { //确保运行的次数是6即出最后一个元素外其他元素都移动一位 arr[i] arr[i - 1]; } arr[0] temp; } } for (int j 0; j arrSize ; j) { printf(%d, arr[j]); } }这是我写的第一个版本这个是在编译器里练习实现的并没有按照题目的要求去完成对应的符合效率的算法。之所以也分享出来是因为我想分享一些不经常写代码的人常常会范的错误注意点一for循环中的运行次数把握不好我们可能常常会在循环的起始条件和结束条件对运行的次数感觉很晕。比如起始条件i0或者i1和结束条件或时运行出来的结果不一样有时容易弄混。分享一个小经验注意点二不要把while循环的括号放在结尾了注意每单句都要写分号。实际上我最开始的代码是这样的#includestdio.h //轮转数组 //思路定义一个数组。 // 这个数组的最后一个元素单独存下前面的元素依次向后移动一位最后将最后一个元素在移动到第一位。 // 把这个过程重复到想要进行的轮数 int main() { int arr[7] { 1,2,3,4,5,6,7 }; int n 3; int i; // 定义轮数以三为例。即把数组的所有元素都向右移动三次 int temp; // 定义一个临时变量用来存放数组的最后一个元素 for (n 3; n 0; n--) //确保轮转的次数是3 { for (i 0; i (arr[sizeof(arr) / sizeof(arr[0])]) - 1; i) { //确保运行的次数是6即出最后一个元素外其他元素都移动一位 temp arr[sizeof(arr) / sizeof(arr[0]) - 1]; arr[i 1] arr[i]; arr[0] temp; } } for (i 0; i (arr[sizeof(arr) / sizeof(arr[0])])-1; i) { printf(%d, arr[i]); } }这么一看实在是惨不忍睹不但思路不清晰有很多的代码写的不言简意赅。比如(arr[sizeof(arr) / sizeof(arr[0])])-1。还有很多逻辑错误比如for (n 3; n 0; n--) //确保轮转的次数是3 { for (i 0; i (arr[sizeof(arr) / sizeof(arr[0])]) - 1; i) { / temp arr[sizeof(arr) / sizeof(arr[0]) - 1]; arr[i 1] arr[i]; arr[0] temp; } }这里面我将最后一个数组元素的存储的存储和赋值都放入了内层循环里面了这样会有一个什么结果这样做会导致内层循环每进行一次就会让最后一个元素放到第一个去而我们想要的是循环每执行一轮的最后一个元素放到第一个去。二、利用函数思想去做这个代码void rotate(int* nums, int numsSize, int k) { //这三个参数是:一个是数组指针一个是数组大小一个是轮转次数。 while (k--) { int temp nums[numsSize - 1]; for (int n numsSize - 1; n 0; n--) { nums[n] nums[n - 1]; } nums[0] temp; } } int main() { int nums[] { 1, 2, 3, 4, 5, 6, 7 }; int k 3; int numsSize sizeof(nums) / sizeof(nums[0]); rotate(nums, numsSize, k); for (int i 0; i numsSize; i) { printf(%d , nums[i]); } return 0;这道题的思路把最后一个数据存储起来把所有的数据整体向后移动一位。然后把最后一个数据移到第一个位置。这是运行一次的效果。那么我们需求轮转k次。那么把这个过程循环k轮就可以了1.正常来说这道题的思路并不难代码可能也不难写但是提交的时候为什么会出现这种情况答案是这种写法的时间复杂度和空间复杂度超出了要求。如果是没有检查我们代码那么有这种报错可能是因为死循环但是我们检查过我们的代码是不可能出现这种错误的。所以只有一种那就是我们的代码效率太低。即时间复杂度太高时间复杂度和空间复杂度分析通过大O阶表示法最后的结果应该是时间复杂度O(n^2)O(1)2.时间复杂度和空间复杂度定义时间复杂度代码执行的基本操作次数随数据规模 n 增长的变化趋势空间复杂度算法运行过程中额外开辟的内存空间随数据规模 n 增长的变化趋势3. 常见复杂度从低到高大O表示名称典型场景O(1)常数阶数组按下标取值O(log n)对数阶二分查找O(n)线性阶单层循环遍历数组O(n log n)线性对数阶快速排序、归并排序O(n²)平方阶双层嵌套循环O(2ⁿ)指数阶斐波那契数列的递归暴力版第三种写法算法逻辑的改造想要挪几位数就直接把数据放在另一个空数据里我想挪几位直接就把前几个数据放在后几个位置上比如想让数组轮转3次就把后三个元素提前一步放到另一个数组的前三位。伪代码编写定义一个无返回值的函数这个函数有nums_A(数组)、n(轮转数)、nums_B(临时变量)代码编写# include stdio.h void rotate(int n, int* nums_A, int* nums_B) { //已知要轮转三次我现在要把后三个元素送到临时数组里面 for (n 3; n 0; n--) { //后三个元素是nums_A[4],nums_A[5],nums_A[6] nums_B[n] nums_A[7 - n]; } for (n 3; n 0; n--) { nums_B[7 - n] nums_A[n]; } } int main() { int n 3; int nums_A[] { 1,2,3,4,5,6,7 }; int nums_B[] { 0 }; int nums_Size sizeof(nums_A) / sizeof(nums_A[0]); rotate(n,nums_A, nums_B); for (int a 0; a nums_Size; a) { printf(%d \n, nums_B[a]); } }这是我写的代码有错误但是让我检查的话我是看不出啊来我写的错误的。欢迎大家给我指出来这样的代码逻辑上似乎也跑的通但是这个思路最优化的解法应该是:遍历第一个数组把第一个数组的所有元素想轮转几次就把数组的元素向后挪几位当移动到第五位时我们的数组在挪位置会越界这里再把(ik)%nums_Size。这样可以覆盖到1234567.这个真想不到(-_-) 唉…最后一步再把num_B的数据赋到num_A# include stdio.h void rotate(int n, int* nums_A, int nums_Size) { int nums_B[nums_Size]; for (int i 0; i nums_Size;i) { nums_B[(i n) % nums_Size] nums_A[i]; } for(int i0;inums_Size;i){ nums_A[i] nums_B[i]; } } int main() { int n 3; int nums_A[] { 1,2,3,4,5,6,7 }; int nums_Size sizeof(nums_A) / sizeof(nums_A[0]); rotate(n, nums_A,nums_Size); for (int a 0; a nums_Size; a) { printf(%d \n, nums_A[a]); } }注意这个代码是对的但是C99标准的变长数组可能会引起编译器不支持小结这里的时间复杂度空间复杂度都是On。这意味着我们是用了空间换时间的操作。因此我们也要找到不牺牲空间复杂度有减少时间复杂度的方法四、第四种写法第三种思路三次逆置。第一次逆置把前四个数据逆转一下第二次把后三个数据逆转一下最后把所有数据逆转一下不要管怎么想的不要问为什么实现这种效果的。逆置怎么做这个题我们只需要一个函数就是逆置逆置。假如我们有这样一个数组1234 。我们可以分为左边和右边分别是left和right。我们让right和left开始循环交换两个指向的值。循环结束条件left比right大。2.怎么完成逆置三次直接把逆置作为函数在真正的轮转函数定义中调用这个函数三次。这三次逆置都是操作在一个数组中所以我们没有临时数组也没有返回值。# includestdio.h void reverse(int left, int right, int* nums) { int temp; while (leftright) { temp nums[right]; nums[right] nums[left]; nums[left] temp; left; right--; } } void rolate(int* nums,int nums_Size,int k) { reverse(0,nums_Size-k,nums); reverse(nums_Size-k,nums_Size,nums); reverse(0,nums_Size,nums); } int main() { int nums[] { 1,2,3,4,5,6,7 }; int nums_Size sizeof(nums) / sizeof(nums[0]); int left 0; int k 3; int right sizeof(nums) / sizeof(nums[0]) - 1; rolate(nums,nums_Size,k); for (int a 0; a nums_Size; a) { printf(%d \n, nums[a]); } }实现了这个逻辑之后这道代码有2个错误第一次逆转应该时nums_Size-1-k第二次逆转的时候应该是nums_Size-1。第三次同理。2.防御性编程思想如果k为10那么我们的代码将会出现nums_Size-k0的情况但是数组里面小于零的下标是不存在的。所以保证k比我们当前数组的长度要小。防止k小于0的方法void rolate(int* nums,int nums_Size,int k) { kk%nums_Size; reverse(0,nums_Size-k-1,nums); reverse(nums_Size-k-1,nums_Size,nums); reverse(0,nums_Size-1,nums);}这是最终没有语法错误的代码# includestdio.h void reverse(int left, int right, int* nums) { int temp; while (leftright) { temp nums[left]; nums[left] nums[right]; nums[right] temp; left; right--; } } void rolate(int* nums,int nums_Size,int k) { kk%nums_Size; reverse(0,nums_Size-k-1,nums); reverse(nums_Size-k,nums_Size-1,nums); reverse(0,nums_Size-1,nums); } int main() { int nums[] { 1,2,3,4,5,6,7 }; int nums_Size sizeof(nums) / sizeof(nums[0]); int left 0; int k 3; int right sizeof(nums) / sizeof(nums[0]) - 1; rolate(nums,nums_Size,k); for (int a 0; a nums_Size; a) { printf(%d \n, nums[a]); } }这个不知道为啥还是报错时间复杂度O(n)空间复杂度O(1) 
长河君 · 2026/9/7 22:14:05 · 阅读 1.2k 数据结构——轮转数组算法题
数据结构-轮转函数算法题今天练习一道算法题该题地址一、思路最简单的代码#includestdio.h //思路定义一个数组。 //这个数组的最后一个元素单独存下前面的元素依次向后移动一位最后将最后一个元素在移动到第一位。 // 把这个过程重复到想要进行的轮数 int main() { int arr[7] { 1,2,3,4,5,6,7 }; int n 3; // 定义轮数以三为例。即把数组的所有元素都向右移动三次 int arrSize sizeof(arr) / sizeof(arr[0]); //计算数组的大小 while (n--) { //确保轮转的次数是3 { int temp arr[arrSize - 1]; for (int i arrSize - 1; i 0; i--) { //确保运行的次数是6即出最后一个元素外其他元素都移动一位 arr[i] arr[i - 1]; } arr[0] temp; } } for (int j 0; j arrSize ; j) { printf(%d, arr[j]); } }这是我写的第一个版本这个是在编译器里练习实现的并没有按照题目的要求去完成对应的符合效率的算法。之所以也分享出来是因为我想分享一些不经常写代码的人常常会范的错误注意点一for循环中的运行次数把握不好我们可能常常会在循环的起始条件和结束条件对运行的次数感觉很晕。比如起始条件i0或者i1和结束条件或时运行出来的结果不一样有时容易弄混。分享一个小经验注意点二不要把while循环的括号放在结尾了注意每单句都要写分号。实际上我最开始的代码是这样的#includestdio.h //轮转数组 //思路定义一个数组。 // 这个数组的最后一个元素单独存下前面的元素依次向后移动一位最后将最后一个元素在移动到第一位。 // 把这个过程重复到想要进行的轮数 int main() { int arr[7] { 1,2,3,4,5,6,7 }; int n 3; int i; // 定义轮数以三为例。即把数组的所有元素都向右移动三次 int temp; // 定义一个临时变量用来存放数组的最后一个元素 for (n 3; n 0; n--) //确保轮转的次数是3 { for (i 0; i (arr[sizeof(arr) / sizeof(arr[0])]) - 1; i) { //确保运行的次数是6即出最后一个元素外其他元素都移动一位 temp arr[sizeof(arr) / sizeof(arr[0]) - 1]; arr[i 1] arr[i]; arr[0] temp; } } for (i 0; i (arr[sizeof(arr) / sizeof(arr[0])])-1; i) { printf(%d, arr[i]); } }这么一看实在是惨不忍睹不但思路不清晰有很多的代码写的不言简意赅。比如(arr[sizeof(arr) / sizeof(arr[0])])-1。还有很多逻辑错误比如for (n 3; n 0; n--) //确保轮转的次数是3 { for (i 0; i (arr[sizeof(arr) / sizeof(arr[0])]) - 1; i) { / temp arr[sizeof(arr) / sizeof(arr[0]) - 1]; arr[i 1] arr[i]; arr[0] temp; } }这里面我将最后一个数组元素的存储的存储和赋值都放入了内层循环里面了这样会有一个什么结果这样做会导致内层循环每进行一次就会让最后一个元素放到第一个去而我们想要的是循环每执行一轮的最后一个元素放到第一个去。二、利用函数思想去做这个代码void rotate(int* nums, int numsSize, int k) { //这三个参数是:一个是数组指针一个是数组大小一个是轮转次数。 while (k--) { int temp nums[numsSize - 1]; for (int n numsSize - 1; n 0; n--) { nums[n] nums[n - 1]; } nums[0] temp; } } int main() { int nums[] { 1, 2, 3, 4, 5, 6, 7 }; int k 3; int numsSize sizeof(nums) / sizeof(nums[0]); rotate(nums, numsSize, k); for (int i 0; i numsSize; i) { printf(%d , nums[i]); } return 0;这道题的思路把最后一个数据存储起来把所有的数据整体向后移动一位。然后把最后一个数据移到第一个位置。这是运行一次的效果。那么我们需求轮转k次。那么把这个过程循环k轮就可以了1.正常来说这道题的思路并不难代码可能也不难写但是提交的时候为什么会出现这种情况答案是这种写法的时间复杂度和空间复杂度超出了要求。如果是没有检查我们代码那么有这种报错可能是因为死循环但是我们检查过我们的代码是不可能出现这种错误的。所以只有一种那就是我们的代码效率太低。即时间复杂度太高时间复杂度和空间复杂度分析通过大O阶表示法最后的结果应该是时间复杂度O(n^2)O(1)2.时间复杂度和空间复杂度定义时间复杂度代码执行的基本操作次数随数据规模 n 增长的变化趋势空间复杂度算法运行过程中额外开辟的内存空间随数据规模 n 增长的变化趋势3. 常见复杂度从低到高大O表示名称典型场景O(1)常数阶数组按下标取值O(log n)对数阶二分查找O(n)线性阶单层循环遍历数组O(n log n)线性对数阶快速排序、归并排序O(n²)平方阶双层嵌套循环O(2ⁿ)指数阶斐波那契数列的递归暴力版第三种写法算法逻辑的改造想要挪几位数就直接把数据放在另一个空数据里我想挪几位直接就把前几个数据放在后几个位置上比如想让数组轮转3次就把后三个元素提前一步放到另一个数组的前三位。伪代码编写定义一个无返回值的函数这个函数有nums_A(数组)、n(轮转数)、nums_B(临时变量)代码编写# include stdio.h void rotate(int n, int* nums_A, int* nums_B) { //已知要轮转三次我现在要把后三个元素送到临时数组里面 for (n 3; n 0; n--) { //后三个元素是nums_A[4],nums_A[5],nums_A[6] nums_B[n] nums_A[7 - n]; } for (n 3; n 0; n--) { nums_B[7 - n] nums_A[n]; } } int main() { int n 3; int nums_A[] { 1,2,3,4,5,6,7 }; int nums_B[] { 0 }; int nums_Size sizeof(nums_A) / sizeof(nums_A[0]); rotate(n,nums_A, nums_B); for (int a 0; a nums_Size; a) { printf(%d \n, nums_B[a]); } }这是我写的代码有错误但是让我检查的话我是看不出啊来我写的错误的。欢迎大家给我指出来这样的代码逻辑上似乎也跑的通但是这个思路最优化的解法应该是:遍历第一个数组把第一个数组的所有元素想轮转几次就把数组的元素向后挪几位当移动到第五位时我们的数组在挪位置会越界这里再把(ik)%nums_Size。这样可以覆盖到1234567.这个真想不到(-_-) 唉…最后一步再把num_B的数据赋到num_A# include stdio.h void rotate(int n, int* nums_A, int nums_Size) { int nums_B[nums_Size]; for (int i 0; i nums_Size;i) { nums_B[(i n) % nums_Size] nums_A[i]; } for(int i0;inums_Size;i){ nums_A[i] nums_B[i]; } } int main() { int n 3; int nums_A[] { 1,2,3,4,5,6,7 }; int nums_Size sizeof(nums_A) / sizeof(nums_A[0]); rotate(n, nums_A,nums_Size); for (int a 0; a nums_Size; a) { printf(%d \n, nums_A[a]); } }注意这个代码是对的但是C99标准的变长数组可能会引起编译器不支持小结这里的时间复杂度空间复杂度都是On。这意味着我们是用了空间换时间的操作。因此我们也要找到不牺牲空间复杂度有减少时间复杂度的方法四、第四种写法第三种思路三次逆置。第一次逆置把前四个数据逆转一下第二次把后三个数据逆转一下最后把所有数据逆转一下不要管怎么想的不要问为什么实现这种效果的。逆置怎么做这个题我们只需要一个函数就是逆置逆置。假如我们有这样一个数组1234 。我们可以分为左边和右边分别是left和right。我们让right和left开始循环交换两个指向的值。循环结束条件left比right大。2.怎么完成逆置三次直接把逆置作为函数在真正的轮转函数定义中调用这个函数三次。这三次逆置都是操作在一个数组中所以我们没有临时数组也没有返回值。# includestdio.h void reverse(int left, int right, int* nums) { int temp; while (leftright) { temp nums[right]; nums[right] nums[left]; nums[left] temp; left; right--; } } void rolate(int* nums,int nums_Size,int k) { reverse(0,nums_Size-k,nums); reverse(nums_Size-k,nums_Size,nums); reverse(0,nums_Size,nums); } int main() { int nums[] { 1,2,3,4,5,6,7 }; int nums_Size sizeof(nums) / sizeof(nums[0]); int left 0; int k 3; int right sizeof(nums) / sizeof(nums[0]) - 1; rolate(nums,nums_Size,k); for (int a 0; a nums_Size; a) { printf(%d \n, nums[a]); } }实现了这个逻辑之后这道代码有2个错误第一次逆转应该时nums_Size-1-k第二次逆转的时候应该是nums_Size-1。第三次同理。2.防御性编程思想如果k为10那么我们的代码将会出现nums_Size-k0的情况但是数组里面小于零的下标是不存在的。所以保证k比我们当前数组的长度要小。防止k小于0的方法void rolate(int* nums,int nums_Size,int k) { kk%nums_Size; reverse(0,nums_Size-k-1,nums); reverse(nums_Size-k-1,nums_Size,nums); reverse(0,nums_Size-1,nums);}这是最终没有语法错误的代码# includestdio.h void reverse(int left, int right, int* nums) { int temp; while (leftright) { temp nums[left]; nums[left] nums[right]; nums[right] temp; left; right--; } } void rolate(int* nums,int nums_Size,int k) { kk%nums_Size; reverse(0,nums_Size-k-1,nums); reverse(nums_Size-k,nums_Size-1,nums); reverse(0,nums_Size-1,nums); } int main() { int nums[] { 1,2,3,4,5,6,7 }; int nums_Size sizeof(nums) / sizeof(nums[0]); int left 0; int k 3; int right sizeof(nums) / sizeof(nums[0]) - 1; rolate(nums,nums_Size,k); for (int a 0; a nums_Size; a) { printf(%d \n, nums[a]); } }这个不知道为啥还是报错时间复杂度O(n)空间复杂度O(1)