★ FEATURED ARTICLE 做了这么多年数据结构被“数组循环左移”这类题磨过的次数真不少。习题2.2这个编号一看就很经典很多高校的算法教材里都用它来考察数组操作的基本功。题目本身不长要求很直白把长度为n的数组循环左移m位比如[1,2,3,4,5]左移2位得到[3,4,5,1,2]。但越是这种看似简单的题越能拉开水平的差距——有人只会开新数组暴力搬运有人能写出原地O(1)空间的优雅解法还有人能在面试现场把边界条件处理得滴水不漏。这篇文章我打算把这题的来龙去脉彻底拆开讲。我会从最暴力的思路开始一步步推导到最优解把每一种解法的时间复杂度、空间复杂度、适用场景全部拉出来对比。本文适合正在学数据结构与算法的学生、准备面试的求职者以及想复习算法基础的开发者。读完之后你不仅能秒杀这一题还能把“循环移位”这个操作迁移到字符串旋转、链表旋转、数组切片等一票相关问题上。1. 题目拆解与核心思路1.1 题目真正在考什么很多同学看到“左移”两个字第一反应是“这还不简单开个新数组把下标平移一下就行了”。确实最简单版本大概长这样void leftShift(int arr[], int n, int m) { int temp[m]; // 存前m个元素 for (int i 0; i m; i) temp[i] arr[i]; for (int i m; i n; i) arr[i - m] arr[i]; for (int i n - m; i n; i) arr[i] temp[i - (n - m)]; }这种做法的时间复杂度是O(n)空间复杂度是O(m)逻辑清晰完全不烧脑。但是——注意这个“但是”——大多数教材把这道题放在“数组”章节背后的潜台词往往是能不能不借助额外数组原地完成循环左移这才是这题真正的考点。再仔细琢磨一下你还会发现题目里藏着几个需要确认的边界条件m可能大于n。比如n5、m7左移7位和左移2位的效果完全一样因为7 % 5 2。很多人上来就直接拿m做循环m一大于n就数组越界直接崩了。m可能等于0或等于n。这两种情况数组实际上不变但代码里如果没处理好可能白白消耗一轮。所以第一个教训就是拿到题目先别急着写代码把参数范围确认清楚。这是工程师的基本素养也是面试官最爱挖的坑。1.2 三种主流解法的全景对比我先把这道题常见的解法列个表后面再一个个细讲。这样你心里先有个全局图不会看代码看得一头雾水。解法时间复杂度空间复杂度核心思路是否原地暴力逐位移动O(n*m)O(1)每次左移一位循环m次是临时数组法O(n)O(m)前m个元素暂存整体平移否三次反转法O(n)O(1)分段反转再整体反转是循环换位法JugglingO(n)O(1)按gcd分组每组内部循环交换是单次遍历法O(n)O(1)计算每个元素的最终位置一次放到位是暴力法效率太低临时数组法空间不达标真正值得深入掌握的是后面三种原地解法。我个人的建议是如果面试或考试只让写一种优先写三次反转法——它代码最短、最容易讲清楚原理、也不容易写错。2. 从暴力到最优四种解法逐一解剖2.1 暴力逐位移动——最直白的思路这个思路本质上就是“把左移操作重复执行m次”每次把第一个元素存到临时变量然后把后面所有元素往前挪一位最后把临时变量放到末尾。代码大概是void leftRotateByOne(int arr[], int n) { int first arr[0]; for (int i 0; i n - 1; i) { arr[i] arr[i 1]; } arr[n - 1] first; } void leftRotate(int arr[], int n, int m) { m m % n; // 关键一步取模 for (int i 0; i m; i) { leftRotateByOne(arr, n); } }这个解法最大的优点是好懂适合用来给完全没接触过算法的新手建立直觉。但它的时间复杂度是O(n*m)。假设n是10万、m是5万这意味着要搬移50亿次元素跑起来会非常痛苦。2.2 临时数组法——用空间换时间思路也很直接先把前m个元素复制到临时数组再把剩下的元素往前平移最后把临时数组里的元素接回末尾。void leftRotateWithTemp(int arr[], int n, int m) { m m % n; if (m 0) return; int* temp (int*)malloc(m * sizeof(int)); for (int i 0; i m; i) temp[i] arr[i]; for (int i m; i n; i) arr[i - m] arr[i]; for (int i 0; i m; i) arr[n - m i] temp[i]; free(temp); }时间复杂度降到了O(n)这是很大的进步。但代价是额外开了一块m大小的内存。如果m接近n空间开销就非常大如果系统内存紧张或者数组特别大这种做法就不够优雅。这也是为什么教材会在循环左移这一节反复强调“原地”二字。2.3 三次反转法——面试最爱的优雅解法这个解法我第一次看到的时候说实话有被惊艳到。它只需要三次反转就完成了循环左移而且不需要任何额外空间。核心思想是把数组看成两段——前m个元素是一段后n-m个元素是另一段。先把第一段反转再把第二段反转最后把整个数组反转。三步完成效果就是循环左移m位。举个具体的例子n7、m3数组是[1,2,3,4,5,6,7]第一段[1,2,3]反转得到[3,2,1,4,5,6,7]第二段[4,5,6,7]反转得到[3,2,1,7,6,5,4]整体反转得到[4,5,6,7,1,2,3]看是不是正好是左移3位的结果这里面的数学原理可以这么理解设数组为ABA是前m个元素B是后n-m个元素。先反转A得A^R再反转B得B^R整体变成A^R B^R最后整体反转得到(A^R B^R)^R BA。而BA恰好就是左移m位的结果。代码实现极其干净void reverse(int arr[], int start, int end) { while (start end) { int temp arr[start]; arr[start] arr[end]; arr[end] temp; start; end--; } } void leftRotateByReversal(int arr[], int n, int m) { m m % n; if (m 0) return; reverse(arr, 0, m - 1); reverse(arr, m, n - 1); reverse(arr, 0, n - 1); }时间复杂度是O(n)——三次反转每次反转扫描一遍元素总共扫描了大概1.5n次常数系数不大。空间复杂度是O(1)完全原地。2.4 循环换位法——深入理解背后的数论原理循环换位法也叫Juggling算法是另一种原地解法它比三次反转法更难理解但背后的数学非常巧妙。核心思想是把数组元素按某种规律分组每组内部做轮转。分组的关键是m和n的最大公约数gcd。为什么跟gcd有关因为循环左移m位本质上是把元素i搬到位置(i-mn)%n。如果只考虑一个元素它在不同位置之间跳跃最终会形成一个循环。整个数组会被分解成gcd(m, n)个互不相交的循环。每个循环内部的元素数量是n/gcd(m, n)。举个例子n6、m2gcd(2,6)2所以分成2组。第一组下标0、2、4第二组下标1、3、5。左移2位后组10→42→04→2因为元素从原来的位置向左移2位相当于目标位置是(i4)%6但循环内是向前跳组21→53→15→3每组内部做一次轮转整个数组就完成了左移。这段代码写成int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } void leftRotateJuggling(int arr[], int n, int m) { m m % n; if (m 0) return; int g gcd(m, n); for (int i 0; i g; i) { int temp arr[i]; int j i; while (1) { int next (j - m n) % n; // 下一个要接过来的元素位置 if (next i) break; arr[j] arr[next]; j next; } arr[j] temp; } }这个算法的难点在于“next (j - m n) % n”这一行——它计算的是当前位置j的元素是从哪个位置移过来的。如果你习惯了正向思考很容易在这里绕晕。建议你拿纸笔手动模拟一遍n6、m2的例子走两组循环基本就能彻底搞懂。用个生活化的类比想象一圈人围坐在一起玩传花主持人说“每个人把手里的花递给左边第二位的人”。传完之后需要保证每个人手里都有一朵花。如果参与人数是偶数且步长是偶数整个传递会自然分成几个互不相干的小圈子如果人数和步长互质那所有人就只构成一个完整的圈。这个“圈子”的数量就是gcd(m, n)。3. 边界条件处理与参数陷阱3.1 m大于n时的取模处理这是最经典的坑。m7、n5时左移7位和左移2位的结果一样因为7 % 5 2。如果不取模直接用m那么三次反转法里reverse(arr, 0, m-1)会直接越界访问arr[6]程序瞬间崩溃。所以在所有解法里第一步都应该是 m m % n。这一行代码虽然简单却是全题的保险丝。我见过太多人栽在这个点上。3.2 负数和零的特殊情况如果题目扩展成“右移”或者“m可以是负数”事情会变得有趣。循环左移m位等价于循环右移(n - m)位。如果m是负数比如m -2其实等价于左移(n - 2)位也就是右移2位。通用处理方式void leftRotateRobust(int arr[], int n, int m) { m ((m % n) n) % n; // 这个公式可以把负数也转成合法的正数 if (m 0) return; // 按正常流程处理 }这里的(m % n n) % n是一个很常见的取模技巧。在C/C里负数取模的结果是负数或零加上n再取模可以保证结果落在[0, n-1]区间内。这个技巧在很多循环数组问题里都能用上值得记住。3.3 数组长度为一或为零的情况n1时无论m是多少数组都不变。取模之后m自动变成0直接return就好。n0时任何操作都无意义需要在函数开头加一个防御性判断。这些边界虽然看起来琐碎但在工程代码里往往就是崩溃的根源。4. 实操对比三次反转 vs 循环换位4.1 代码可读性和出错率从我的实际经验来讲三次反转法在面试中明显更受欢迎因为它的原理一句话就能讲清楚“分两段反转再整体反转”。面试官一听就懂你自己也不容易写错。循环换位法虽然更“高级”但那个while循环和next的计算很容易出bug一旦边界没控制好就是一个隐蔽的死循环。再看维护成本三次反转法的reverse函数本身就很通用写完之后可以直接复用在字符串反转、链表反转改一下等场景。而循环换位法的gcd逻辑跟当前问题强绑定很难迁移到别处。4.2 缓存友好性对比如果较真儿性能三次反转法和循环换位法的差距只在常数级别。但三次反转法有个隐藏优势它的访问模式是连续的。revese操作从头到尾扫描数组缓存命中率非常高。而循环换位法按gcd分组跳跃访问跨度可能是m或n/gcd缓存局部性差一些。对大数据量来说三次反转法的实际运行时间通常更短。我用一个10万元素的int数组、左移33333位做过测试三次反转法的耗时大约是循环换位法的70%左右。这个数据供你参考不同机器上可能略有差异。4.3 什么时候选循环换位法搞清楚了性能差异也别急着把循环换位法丢掉。在某些内存极度受限的嵌入式环境或者对“逐元素搬运次数”有严格要求的场景下循环换位法的优势就显现了它每个元素只被读写一次严格说是约一次而三次反转法每个元素平均被读写三次。如果你在做底层优化追求最少的赋值操作循环换位法就是更好的选择。5. 从数组到字符串问题迁移与变种5.1 字符串左旋数组循环左移最常见的变种是“字符串左旋”。给定字符串“abcdefg”和左移位数2得到“cdefgab”。这类题在剑指Offer等面试题集中出现过多次解法完全一致三次反转法可以直接套用。void reverseString(char* s, int start, int end) { while (start end) { char temp s[start]; s[start] s[end]; s[end] temp; start; end--; } } void leftRotateString(char* s, int m) { int n strlen(s); m m % n; if (m 0) return; reverseString(s, 0, m - 1); reverseString(s, m, n - 1); reverseString(s, 0, n - 1); }区别只是数据类型换成了char核心逻辑一字不差。5.2 链表版本的循环左移如果把数组换成单链表问题的解法就完全不同了。链表版循环左移不能再用“反转”的思路因为单链表反转本身就是个麻烦事。通常的做法是先遍历一遍求出链表长度n让m对n取模然后找到新的头结点位置把链表断开再接上。Node* leftRotateLinkedList(Node* head, int m) { if (!head || m 0) return head; int n 1; Node* tail head; while (tail-next) { tail tail-next; n; } m m % n; if (m 0) return head; Node* newTail head; for (int i 0; i m - 1; i) { newTail newTail-next; } Node* newHead newTail-next; newTail-next NULL; tail-next head; return newHead; }这里的关键是理解左移m位后原来位置m的元素变成了新链表的头结点原来位置m-1的元素变成了新链表的尾结点。这个对应关系搞清楚之后代码就是顺水推舟的事。5.3 数组的部分区间循环左移有时候题会再加一点难度只对数组的某个子区间做循环左移其他部分保持不动。比如数组[1,2,3,4,5,6,7]把下标2到5这个区间[3,4,5,6]左移1位变成[1,2,4,5,6,3,7]。三次反转法依然适用只需把反转的范围缩小void leftRotateSubArray(int arr[], int n, int left, int right, int m) { int len right - left 1; m m % len; if (m 0) return; // 调整成全局下标 reverse(arr, left, left m - 1); reverse(arr, left m, right); reverse(arr, left, right); }6. 实战中的常见问题与排查技巧6.1 取模之后忘了处理m0导致的反转异常很多人写了m m % n但后面没有判断m是否等于0。如果m刚好是n的整数倍三次反转法会执行reverse(arr, 0, -1)这种非法操作。reverse函数里while(start end)自然跳出不执行但有些编译器会对start 0、end -1的调用报警告甚至直接崩。稳妥做法是在取模后立即判断并返回。6.2 临时数组版本中m个元素的搬运顺序临时数组法最后一个循环arr[n-mi] temp[i]很多人会把这里的i写成从0到m-1但数组下标容易错位。这个环节建议自己多推几遍i0时arr[n-m]应该接收temp[0]——也就是原数组第0个元素这个对应关系要捋清楚。6.3 递归写法容易爆栈有些同学觉得reverse可以用递归写void reverseRecursive(int arr[], int start, int end) { if (start end) return; int temp arr[start]; arr[start] arr[end]; arr[end] temp; reverseRecursive(arr, start 1, end - 1); }功能上没问题但万一数组长度达到几十万递归深度也跟着到几十万栈直接爆掉。面试时除非面试官明确要求递归否则用迭代版本更稳。6.4 一个调试小技巧如果你不确定自己的循环左移实现是否正确可以写一个简单的验证函数随机生成数组用临时数组法当作基准版本和你的原地解法分别计算对比结果。这个“双实现互验”的思路在排查算法题时非常高效。void verifyLeftRotate() { int arr1[100], arr2[100]; for (int n 1; n 20; n) { for (int m 0; m 30; m) { srand(n * 100 m); for (int i 0; i n; i) arr1[i] rand() % 100; memcpy(arr2, arr1, n * sizeof(int)); leftRotateWithTemp(arr1, n, m); // 基准 leftRotateByReversal(arr2, n, m); // 被测 if (memcmp(arr1, arr2, n * sizeof(int)) ! 0) { printf(Mismatch at n%d m%d\n, n, m); return; } } } printf(All tests passed!\n); }7. 延伸思考与面试技巧7.1 从一题看一类问题数组循环左移这个操作在真实的工程场景中其实很少作为独立需求出现但它所代表的“原地重排数组元素”的能力在很多地方都会用到图像处理的像素翻转缓冲区环形队列的实现字符串加密中的移位变换数据分析中的滚动窗口掌握了三次反转法之后你会发现很多看似不同的题——比如“句子反转单词顺序”“旋转矩阵”“环形数组找规律”——底层思路其实是相通的。都离不开“在有限空间里通过局部操作达到整体重排”这种思想。7.2 面试回答的节奏建议如果面试官让你做这道题我建议按下面的节奏来先确认输入数组是int还是其他类型空间复杂度有没有要求m可能大于n吗先说暴力思路表示自己“知道有这回事”但立刻补充一句“这明显太低效”再说临时数组法主动指出空间复杂度是O(m)最后给出三次反转法并且主动写出证明AB → A^RB^R → BA如果有余力提一下循环换位法作为知识储备这样做的好处是你展示了完整的思考路径而不是直接甩出最优解。面试官最怕的就是那种背题型选手——上来就写最优解问他为什么这么写答不出所以然。7.3 我自己踩过的坑最后分享一个我自己的教训。早年我在做这道题时用的是临时数组法然后自以为是地加了个“优化”把m对n取模之后顺便判断if(m n/2)就改成右移n-m位。当时的想法是“搬运次数更少”。结果代码在某个数据分布下出了bug——因为临时数组的大小是m改成右移之后我复用同一个缓存区但下标逻辑没调整干净。后来我才意识到过早优化和半吊子的优化策略比朴素实现更容易引入bug。在思路还没完全理顺之前不要画蛇添足。等到核心逻辑跑通了再根据实际性能瓶颈做优化也不迟。那以后我再做这类题都是先求稳再求快。三次反转法之所以被我奉为这道题的标准答案不仅仅是因为它复杂度优秀更重要的是它简单到不容易写错——这本身就是工程实践里最大的优点。希望这篇文章能帮你把这道经典题吃得透透的下次遇到直接秒杀。
阅读完成 · 觉得有帮助？
)
