✅ PAT 乙级题目讲解1008《数组元素循环右移问题》摘要本文以 PAT 乙级 1008 题《数组元素循环右移问题》为例详细讲解了三次翻转法实现数组就地循环右移的核心思路。文章提供了手写reverse函数与使用 C STLreverse的两种实现方案分析了常见错误并总结了时间复杂度 O(n)、空间复杂度 O(1) 的高效解法的思维拓展方向。 题目简介本题要求将一个长度为NNN的整数数组循环右移MMM位。所谓“循环右移”即将数组后MMM个元素移至最前面其余元素顺序后移。题目特别要求不能使用额外数组空间即就地操作这使得我们必须在原数组上完成操作且尽量减少数据移动次数。 样例分析输入6 2 1 2 3 4 5 6分析过程原数组[1, 2, 3, 4, 5, 6]循环右移 2 位后变为[5, 6, 1, 2, 3, 4]输出为5 6 1 2 3 4 解题思路 变量说明变量名含义n数组长度m右移位数注意需m % na[i]第i个数组元素✅方法一暴力法不推荐每次循环将最后一个元素插入最前面其余元素依次后移重复MMM次。时间复杂度为O(MN)O(MN)O(MN)效率极低题目已明确不推荐此法。✅方法二高效正解 —— 三次翻转法 核心思想循环右移MMM位等价于把数组分成两段前n−mn-mn−m个元素后mmm个元素将这两段分别翻转最后整体再翻转一次即可达到目标。 推导过程以n 6, m 2为例原数组[1 2 3 4 5 6]分段前段 A [1 2 3 4]后段 B [5 6]执行三次翻转翻转前段[4 3 2 1][5 6]翻转后段[4 3 2 1][6 5]整体翻转[5 6][1 2 3 4]✅✅ 解法一手写reverse函数 函数设计我们手动实现一个区间翻转函数voidreverse(intl,intr){for(intil,jr;ij;i,j--){swap(a[i],a[j]);}}注意区间为闭区间[l, r]使用双指针向中间逼近、两两交换。✅ 完整代码手写翻转函数#includebits/stdc.husingnamespacestd;intn,m,a[105];voidreverse(intl,intr){// [l, r]for(intil,jr;ij;i,j--){swap(a[i],a[j]);}}intmain(){cinnm;m%n;// 防止 m n 越界for(inti0;in;i){cina[i];}// 三次翻转reverse(0,n-m-1);// 翻转前 n-m 段reverse(n-m,n-1);// 翻转后 m 段reverse(0,n-1);// 整体翻转for(inti0;in;i){couta[i](in-1? :);}return0;}✅ 解法二使用 STLreverse函数 参数注意事项reverse(a, a n)使用的是地址指针其参数是左闭右开区间即[first, last)想翻转[L, R]实际写法是reverse(a L, a R 1)。✅ 完整代码调用标准库#includebits/stdc.husingnamespacestd;intn,m,a[105];intmain(){cinnm;m%n;for(inti0;in;i){cina[i];}// 三次翻转STLreverse(a,an-m);// 前段 [0, n-m-1]reverse(an-m,an);// 后段 [n-m, n-1]reverse(a,an);// 整体翻转for(inti0;in;i){couta[i](in-1? :);}return0;} 常见错误提醒错误类型具体表现未对m取模可能导致下标越界m % n必不可少输出末尾多空格需通过i n - 1控制空格输出STL 参数写错reverse(a, a n)是地址区间不是下标自定义 reverse 范围错误注意是否为闭区间[l, r]双指针写法容易 off-by-one✅ 总结归纳本题核心是理解循环右移 三段翻转推荐熟练掌握两种写法手写 STL此技巧广泛用于数组与字符串的旋转操作时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(1)O(1)高效且符合题目要求。 思维拓展类似方法可处理循环左移问题翻转顺序不同三次翻转思想也可应用于字符串、链表、矩阵行列等结构思考如何将该算法推广到部分旋转、滑动窗口等问题。