最近后台好几个读者都在问同一道题就是数据结构教材里的习题2.2 数组循环左移。这道题在考研408、各类算法笔试和面试里都反复出现看着简单真正手写的时候却很容易翻车。今天把这道题彻底拆开讲透题目到底在考什么、四种解法各自怎么设计、完整代码怎么写、边界条件怎么处理、实际踩坑怎么排查一次说清楚。不管你是在备战408、准备机试还是单纯想补一补数组操作的底子这篇都能直接上手。1. 题目解读与思路拆解1.1 先弄懂循环左移在说什么数组循环左移简单说就是把数组里的所有元素整体向左移动 k 个位置左边超出去的元素绕回数组末尾。举一个最直观的例子数组[1, 2, 3, 4, 5]循环左移 2 位结果是[3, 4, 5, 1, 2]。你可以把它想象成一个环形转盘上的数字转盘向左转了两格原本指针指到的数字就被后面的数字顶上来最前面的数字沉回到转盘尾部。这个环形的概念很关键它不是简简单单把每个元素往前挪一位而是要把越界的元素绕回开头所以实现的时候绕不开取模运算。用数学语言描述原数组是a[0..n-1]结果数组是b那么b[i] a[(i k) % n]其中%是取模。注意这里(i k) % n的含义是新数组的第i个位置要放的是原数组第(i k)个位置的值越界时就回绕。这个公式就是整道题的地基后面所有解法本质上都是对这个公式的不同落地方式。题目还有一个隐藏的变量关系需要先想清楚k可能比n大可能等于0在个别扩展题里甚至可能是负数。如果k 8, n 5左移 8 位和左移 3 位的效果完全相同所以动手写代码前最好先做一步归一化k k % n如果k为负数还要再调整成k (k % n n) % n。这一步看起来不起眼但很多错误都出在没处理它。1.2 为什么这道题值得认真做这道题之所以经典不只是因为它出现在教材习题里而是它表面上只考一个数组移动实际上把好几个核心能力点全串起来了索引公式推导、取模运算的运用、原地修改时的覆盖保护意识、时间和空间复杂度之间的权衡、以及代码边界处理。这些恰恰是笔试和面试最常考察的基本功。我见过不少同学背过链表反转、背过快速排序却在这道简单的数组题上栽跟头原因很真实数组题没有复杂的指针操作反而容易让人放松警惕结果一写就错。尤其当你选择直接在原数组上移的解法时如果不小心覆盖了还没用到的元素整个数组就废了。这种隐蔽的错误比明晃晃的语法错误更难发现。针对这道题业界和教材里总结出了几种经典解法我把它们放在一个表里直接对比解法时间复杂度空间复杂度是否原地代码量推荐场景暴力模拟O(n * k)O(1)是极少初学理解辅助数组O(n)O(n)否极少内存充足、求快三次反转O(n)O(1)是少面试、笔试首选环状替换O(n)O(1)是中进阶、追求最小交换次数注意时间复杂度和空间复杂度是同一个榜单里最核心的两个维度。如果面试官明确说不能用额外数组那暴力模拟和辅助数组就要排除掉剩下三次反转和环状替换两个正解。如果他又说尽量减少元素移动次数那环状替换的优势就体现出来了。按这个思路去准备你就不只是会写一种解法而是能根据题目约束从容选型。2. 几种经典解法原理与选择2.1 方法一暴力模拟适合建立直觉暴力模拟的思路最直白左移一位就相当于把arr[0]存起来其余元素全部往前挪一格最后把存起来的arr[0]放到数组末尾。左移k位就把这个操作重复k次。代码写出来长这样void leftShiftOnce(int arr[], int n) { int temp arr[0]; for (int i 1; i n; i) { arr[i - 1] arr[i]; } arr[n - 1] temp; } void leftRotateBySimulate(int arr[], int n, int k) { if (n 1 || k 0) return; k k % n; for (int i 0; i k; i) { leftShiftOnce(arr, n); } }这个解法唯一的价值是帮初学者理解移动本身的语义数组是一个连续的内存块元素前移本质上是从前到后逐个赋值。但它的致命弱点是时间复杂度。每左移一位要移动n - 1个元素移动k次就是O(n * k)。当n 100000、k 50000时要执行约 50 亿次赋值跑起来体感就是卡死。所以它只适合小规模数据或课堂演示千万别带到机试里去。2.2 方法二辅助数组空间换时间的关键一招既然暴力法慢在重复移动那就用空间换时间先复制一份原数组再按b[i] a[(i k) % n]一次性把每个位置填对。虽然牺牲了O(n)的额外空间但时间复杂度直接降到O(n)代码也非常短。void leftRotateByAux(int arr[], int n, int k) { if (n 1 || k 0) return; k k % n; int temp[n]; for (int i 0; i n; i) { temp[i] arr[i]; } for (int i 0; i n; i) { arr[i] temp[(i k) % n]; } }这里的核心就是(i k) % n这个取模操作。很多同学会问为什么不直接写成temp[i k]因为当i k超过n时数组越界了。取模的本质就是把已经出去的元素映射回数组开头这也是循环二字的代码体现。这个方法的优点是逻辑清晰几乎不可能写错缺点是额外数组多了n个元素的空间开销。如果题目没有限制空间或者说你可以另开一个结果数组那直接用这个方法非常稳。我个人刷题时如果只是想快速验证思路也会优先写这个版本等确认无误再优化成原地版本。2.3 方法三三次反转面试官最期待看到的解接下来是被使用频率最高、也是面试官最希望看到的三次反转法。它的核心思想非常巧妙把数组分成两段第一段是前k个元素第二段是剩下的n - k个元素。分别反转这两段再整体反转整个数组左移效果就出来了。还用[1, 2, 3, 4, 5]、左移k 2举例原始数组 [1, 2, 3, 4, 5] 反转前k个 [2, 1, 3, 4, 5] 反转后n-k个 [2, 1, 5, 4, 3] 整体反转 [3, 4, 5, 1, 2]可以看到最后结果完全正确。为什么反转能达成循环左移可以从分组角度看左移k位的本质就是把原数组的前k个元素挪到末尾而后n - k个元素挪到开头。每一段内部顺序保持不变但两段交换了位置。反转两段再整体反转恰好完成了这个段交换而且全程不需要额外数组。代码实现很简洁只需要一个reverse辅助函数void reverse(int arr[], int left, int right) { while (left right) { int temp arr[left]; arr[left] arr[right]; arr[right] temp; left; right--; } } void leftRotateByReverse(int arr[], int n, int k) { if (n 1 || k 0) return; k k % n; reverse(arr, 0, k - 1); reverse(arr, k, n - 1); reverse(arr, 0, n - 1); }这段代码的时间复杂度是O(n)空间复杂度是O(1)因为它只是首尾交换没有占用额外数组。如果你把reverse中的left right不小心写成left right通常也不会报错但会在中间元素上做一次无意义的自我交换属于小瑕疵。真正需要注意的是区间边界前k个是0到k - 1后n - k个是k到n - 1中间不能有重叠也不能有遗漏。一个很实用的自查方法是算区间长度第一个区间长度是(k - 1) - 0 1 k第二个区间长度是(n - 1) - k 1 n - k加起来正好是n。2.4 方法四环状替换追求极致交换次数环状替换法也叫juggling algorithm翻译过来就是抛球杂技它像杂技演员不断把球抛向下一个位置一样把每个元素直接放到正确的最终位置从而减少不必要的重复移动。写代码之前我要把它的推导过程讲清楚否则你只是背代码换个方向就不会了。回忆我们反复用的公式新数组的第i个位置应该放旧数组第(i k) % n个元素。也就是说从位置0出发0位置的正确值来自(0 k) % n位置那我就把(0 k) % n位置的值搬到0空出来的(0 k) % n位置又应该由它的下一个位置((0 k) % n k) % n的值来填。如此循环搬运直到回到起点0再把最初保存的arr[0]放进最后一个空位。用[1, 2, 3, 4, 5]、k 2手动推一遍保存 arr[0] 1 prev 0next (0 2) % 5 2arr[0] arr[2] 3 prev 2next (2 2) % 5 4arr[2] arr[4] 5 prev 4next (4 2) % 5 1arr[4] arr[1] 2 prev 1next (1 2) % 5 3arr[1] arr[3] 4 prev 3next (3 2) % 5 0回到起点arr[3] 1最终得到[3, 4, 5, 1, 2]完全正确。这个例子中gcd(5, 2) 1所以一轮就能覆盖所有位置。但当n和k不互质时一次回圈走不到所有元素需要换一个起点再来一轮比如n 6, k 4gcd(6, 4) 2就需要从0和1分别出发两轮。实现这个算法有两个思路。正统做法是预计算gcd(n, k)作为轮数代码稍微复杂更简单的写法是用一个计数器count记录已正确放置的元素个数每轮从某个start出发走到回到start就换下一个start直到count nvoid leftRotateByJuggling(int arr[], int n, int k) { if (n 1 || k 0) return; k k % n; int count 0; int start 0; while (count n) { int cur start; int prevVal arr[start]; do { int next (cur k) % n; int temp arr[next]; arr[next] prevVal; prevVal temp; cur next; count; } while (cur ! start); start; } }这里有一个容易绕晕的细节每次循环里我们是从prevVal携带上一步的值把arr[next]覆盖后再把arr[next]的原值作为下一轮要搬运的值所以prevVal和temp的交换顺序不要写反。如果你觉得这个版本有点绕可以直接用gcd版本的实现两者效果一样。环状替换的唯一优势是每个元素最多只被移动一次交换次数是理论最优缺点是想清楚它为什么能覆盖所有位置需要一定脑力写错后排查也比较费劲。所以在实际面试里我更推荐先用三次反转法写出来如果面试官追问能不能减少移动次数再把环状替换搬出来。3. 实操完整代码与边界测试3.1 三种核心方案的完整可运行代码为了方便你直接跑实验我把辅助数组、三次反转和环状替换整合到一段 C 代码里用同一个测试函数验证结果。注意这里用的是 C99 变长数组如果你的编译器比较老把temp[n]改成动态内存分配即可。#include stdio.h void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } void reverse(int arr[], int left, int right) { while (left right) { int temp arr[left]; arr[left] arr[right]; arr[right] temp; left; right--; } } void leftRotateByAux(int arr[], int n, int k) { if (n 1 || k 0) return; k k % n; int temp[n]; for (int i 0; i n; i) { temp[i] arr[i]; } for (int i 0; i n; i) { arr[i] temp[(i k) % n]; } } void leftRotateByReverse(int arr[], int n, int k) { if (n 1 || k 0) return; k k % n; reverse(arr, 0, k - 1); reverse(arr, k, n - 1); reverse(arr, 0, n - 1); } void leftRotateByJuggling(int arr[], int n, int k) { if (n 1 || k 0) return; k k % n; int count 0; int start 0; while (count n) { int cur start; int prevVal arr[start]; do { int next (cur k) % n; int temp arr[next]; arr[next] prevVal; prevVal temp; cur next; count; } while (cur ! start); start; } } int main() { int arr[] {1, 2, 3, 4, 5}; int n 5; int k 2; int arrAux[] {1, 2, 3, 4, 5}; leftRotateByAux(arrAux, n, k); printf(aux: ); printArray(arrAux, n); int arrRev[] {1, 2, 3, 4, 5}; leftRotateByReverse(arrRev, n, k); printf(reverse: ); printArray(arrRev, n); int arrJug[] {1, 2, 3, 4, 5}; leftRotateByJuggling(arrJug, n, k); printf(juggling: ); printArray(arrJug, n); return 0; }运行结果aux: 3 4 5 1 2 reverse: 3 4 5 1 2 juggling: 3 4 5 1 2三种方法输出一致说明思路基本正确。但我必须强调仅用这一个用例远远不够下面一节会专门讲边界测试。3.2 边界条件与参数选择k 不能直接拿来用写这类题最容易翻车的地方就是没有对k做归一化处理直接拿原始的k去移动。请你一定记住在代码开头加上这两行if (n 1 || k 0) return; k k % n;它们分别处理了三种情况n 1数组为空或只有一个元素左移任何位结果不变直接返回避免后续reverse(arr, 0, k - 1)出现left 0, right -1这种非法区间。k 0不移动直接返回。k k % n把超过数组长度的移动次数折算成等效的短位移避免循环体执行过多轮。很多面试代码里不会刻意写n 1的分支但当你传入空数组时k k % n本身就是除零错误所以这个分支是保护性必需。即使是k为负数的情况也应该在取模前做处理最简单的做法是k (k % n n) % n保证k落在0到n - 1的闭区间。我再强调一下左移和取模方向的关系。如果题目要求循环左移k位对应公式是(i k) % n如果要求循环右移k位对应公式是(i - k n) % n或者等价地看成左移n - k位。很多同学会把和-记反一个小技巧是先假想k 1沿数组推一遍位置变化再总结规律。3.3 实测运行与复杂度对比为了让你直观感受不同解法的差距我构造了一个稍微大一点的用例n 100000、k 50000。理论上暴力法要移动50000 * 99999 ≈ 5e9次在我的机器上跑完大约需要十几秒而三次反转法和环状替换法都是毫秒级完成。这就是为什么数据结构课程里要反复强调复杂度的意义数据规模一大肉眼可见地拉开差距。我把三种解法的复杂度结论再汇总一次解法时间复杂度空间复杂度移动次数稳定性推荐度暴力模拟O(n * k)O(1)n * k 次高低辅助数组O(n)O(n)n 次复制 n 次写回高中三次反转O(n)O(1)约 1.5n 次交换高高环状替换O(n)O(1)n 次搬运高中高请注意三次反转和环状替换虽然都是O(n)时间但三次反转的实际交换次数大约是n的 1.5 倍而环状替换恰好是n次。如果你在嵌入式这类对执行次数敏感的场景里环状替换会更合适但如果你只是为了通过笔试三次反转的代码更短、更好背、更好改综合优势更强。4. 常见问题与排查技巧实录4.1 取模方向搞反最典型的错误就是把左移写成右移的公式。有人在刷题时写出了这样的代码// 错误示范左移却用减法取模 for (int i 0; i n; i) { arr[i] temp[(i - k n) % n]; }初看好像没问题但代入[1, 2, 3, 4, 5]、k 2时会发现结果变成[4, 5, 1, 2, 3]这其实是右移 2 位。原因是(i - k n) % n描述的是把当前位置的元素放到哪儿和从哪儿取值是相反的两个方向。当你用数组下标推演时只要混淆了值从哪里来和值到哪里去结果就反了。我给你的排查方法是整个循环里只选一个角度思考。如果你写的是arr[i] temp[srcIndex]那么srcIndex就必须是新下标i加大k的方向如果你写的是tmp[destIndex] arr[i]那么destIndex必须是旧下标i减k的方向。选定一个角度后用i 0, k 2, n 5代一遍马上就能发现方向对不对。4.2 原地覆盖导致数据丢失很多初学者一上来就想省空间直接写// 错误示范直接原地覆盖 for (int i 0; i n; i) { arr[i] arr[(i k) % n]; }初看很合理但实际操作时arr[2]的值被提前覆盖掉后面需要用它放到arr[0]时已经不是原来的值了。还是用[1, 2, 3, 4, 5]、k 2推演i 0时把arr[2] 3赋给arr[0]数组变成[3, 2, 3, 4, 5]i 1时把arr[3] 4赋给arr[1]数组变成[3, 4, 3, 4, 5]继续下去原数组的值已经被污染得面目全非。最后得到的数组完全不对。这个错误告诉我们一个通用规则在数组原地操作里如果新位置和旧位置有交叉覆盖必须先想好怎么保护那些还没有被读取但即将被覆盖的值。辅助数组方案是从根上避免这个问题反转法和环状替换则是通过分段处理和缓存一个值来规避。以后你写任何平移删除连续元素这类题目时都要条件反射地想到覆盖顺序的问题。4.3 反转区间越界与空数组崩溃反转法虽然代码少但区间边界一定要写对尤其是k取模后可能为 0。如果k 0第一段区间是[0, -1]reverse函数里left right不成立虽然不崩溃但逻辑怪更危险的是数组为空时n 0直接执行k k % n就会除零崩溃。所以我在所有解法开头都写了if (n 1 || k 0) return;这不是冗余是保命。另一个区间错误是分段的接缝处。假设k 2, n 5有人会把第二段写成reverse(arr, k 1, n - 1)也就是从下标 3 开始反转漏掉了下标 2。验证方法很简单两段区间长度之和必须等于n。第一段[0, k-1]长度是k第二段[k, n-1]长度是n - k相加正好是n。如果求和不对说明边界写错了改回[k, n-1]即可。4.4 容易踩的隐藏坑负数 k、k 大于 n、动态数组尺寸这一节我再列一个实战速查表方便你写完代码立刻自查输入情况正确做法常见错误k n先k k % n再移动直接循环 k 次超时k 0k (k % n n) % n归一化直接% n结果仍为负数n 0函数开头直接返回执行k % n除零崩溃n 1函数开头直接返回反转区间[0, -1]逻辑异常k 0函数开头直接返回多做无意义反转这些都是我实际调试中遇到过的场景。有一次我在机试环境里没处理n 0测试用例一上来就是空数组程序直接崩了白白丢分。从那以后我写任何数组工具函数的第一行都会习惯性地做空数组和单元素数组的短路判断这个习惯可以帮你避开大量隐蔽的运行时错误。5. 从这道题延伸出去的经验5.1 数组题的基本功从一维到二维、指针变体循环左移只是一维数组操作里的一个点但它牵出来的基本功可以延伸到很多相关话题。比如你会在学习过程中遇到指针数组和数组指针的区分指针数组是一个数组里面存的是指针数组指针是一个指针指向一个数组。这两个概念在面试里被问到的频率极高如果你连它们都还没分清那数组循环左移只能算是热身。再比如二维数组循环左移乍一看和这道题无关但如果你理解了内存连续性就能想到两种思路一是按行整体左移二是把二维数组按行扁平化成一维数组后再循环左移最后再恢复成二维形状。后者在思维上更接近指针当一维用的操作对理解数组的内存布局非常有帮助。还有字符数组和字符串数组的循环移动。C 语言里字符串本质是字符数组整体循环左移的逻辑一模一样只是要注意字符串结尾的\0不能参与移动否则输出就乱了。这在某些字符串处理题里是经典变体解法同样是先左移再补\0。5.2 我的实测心得与教学体会我自己带过不少备考的同学刷这道题最常听到的反馈是明明看懂了一写就错。我总结下来真正要过的坎只有三个一是能不能写出(i k) % n这个索引公式二是在原地操作时能不能意识到覆盖问题三是reverse区间能不能一次写对。如果你刷完这道题能独立回答这三个问题那说明这道题你真的吃透了。一个我屡试不爽的学习方法是无论看到什么算法题先不要急着写代码而是拿一个小数组、手动推演一遍全过程把每一步的数组状态写在纸上。推演n 5, k 2的三次反转和环状替换你会发现很多我以为懂了但实际没懂的细节。这个方法尤其适合数组和链表这类可视化程度高的问题花两分钟做推演能省下二十分钟的调试时间。最后分享一个刷题小技巧写测试用例时不要只测标准情况还要主动构造k 0、k n、k n 3、数组为空、数组只有一个元素、甚至k为负数的输入。你的代码如果能稳定通过这一串边界测试那机试的时候基本不会在这类题上失分。数组循环左移看起来是个不起眼的小题但把它练透之后你会发现自己在处理所有下标变换类问题时都会自信很多。