1. 从一道“简单”的蓝桥杯真题说起ALGO-970 数组移动如果你正在准备蓝桥杯或者想通过算法题来巩固C/C基础那么“数组移动”这类题目绝对是你绕不开的经典。ALGO-970这道题乍一看名字平平无奇不就是把数组里的元素挪个位置吗很多新手可能会想这有什么难的一个循环不就搞定了但恰恰是这种“看起来简单”的题目最容易在细节上翻车比如边界条件处理、移动方向、原地操作还是借助辅助空间每一个选择都直接关系到代码的正确性和效率。我见过不少同学在更复杂的动态规划、图论题上能侃侃而谈却在这种基础数组操作上因为一个下标越界或者逻辑混淆而卡住半天。今天我们就以这道题为引子不光是解出它更要深挖“数组移动”这个操作背后所蕴含的编程思维、边界陷阱以及多种解法的权衡让你真正吃透这类基础但至关重要的算法操作。2. ALGO-970 数组移动题意解析与核心需求拆解首先我们需要明确题目到底要求我们做什么。虽然原题的具体描述没有给出但结合“数组移动”这个标题以及蓝桥杯ALGO系列题目的风格我们可以合理推断出几种常见的考察形式。ALGO系列通常考察基础算法和编程能力“数组移动”无外乎以下几种经典场景循环左移/右移这是最经典的数组移动问题。给定一个数组和一个整数k要求将数组中的元素向左或向右循环移动k个位置。例如数组[1,2,3,4,5]循环左移2位后变为[3,4,5,1,2]。特定规则移动可能根据某种规则如奇数在前偶数在后、零元素移动到末尾等重新排列数组元素。基于索引的交换移动题目可能给出一个索引序列要求按照这个序列来交换或移动元素。为了进行最通用和深入的探讨我们假设ALGO-970考察的是第一种也是最常见、最核心的数组循环左移问题。我们设定题目描述为给定一个长度为N的整数数组A和一个非负整数K要求将数组A中的元素循环左移K位。要求尽可能高效并且最好能原地修改数组即不使用额外的数组存储结果。明确了问题我们再来拆解核心需求与难点核心操作将数组视为一个环形结构将开头的K个元素“搬”到数组的末尾。边界处理如果K大于数组长度N怎么办移动N位等于没动所以有效的移动位数是K % N。这是第一个容易忽略的坑。如果K等于0或者K是N的整数倍数组应保持不变。移动过程中如何保证元素不被覆盖这是实现算法的关键。效率要求题目通常有时间和空间限制。最直观的“一次移动一位移动K次”的方法时间复杂度是O(N*K)当K很大时效率极低。我们需要寻找O(N)时间复杂度的解法。原地操作这是体现算法功力的地方。能否在不使用另一个大小相同的数组的前提下完成移动接下来我们将围绕这些需求展开几种不同思路的解法并深入分析其原理和实现细节。3. 解法一暴力法——理解问题本质的起点任何复杂问题的解决都可以从一个最简单、最直观的想法开始。对于循环左移K位最直接的思路就是模拟移动过程。我们把“左移一位”这个操作封装成一个函数然后执行K次。3.1 单次左移的实现如何左移一位呢我们需要把数组的第一个元素取出来暂存然后将第2个到第N个元素依次向前移动一位最后把暂存的第一个元素放到数组末尾。void leftRotateByOne(int arr[], int n) { int temp arr[0]; // 暂存第一个元素 for (int i 0; i n - 1; i) { arr[i] arr[i 1]; // 前移 } arr[n - 1] temp; // 第一个元素放到末尾 }3.2 执行K次移动有了单次移动的函数主逻辑就非常简单了void leftRotate(int arr[], int n, int k) { k k % n; // 关键步骤处理k大于n的情况 for (int i 0; i k; i) { leftRotateByOne(arr, n); } }3.3 复杂度分析与适用场景时间复杂度单次左移需要遍历n-1个元素执行k次所以总的时间复杂度是O(n * k)。当k接近n时复杂度接近O(n²)。空间复杂度我们只用了常数级别的额外空间temp变量所以是O(1)。注意虽然这个方法空间效率高但时间效率在k较大时非常差。在蓝桥杯等竞赛中如果数据规模n和k较大这种方法几乎必然会导致超时Time Limit Exceeded。它最大的价值在于帮助我们清晰地理解“循环左移”究竟在做什么是思维起点而非最终答案。4. 解法二使用辅助数组——空间换时间的典型策略当时间成为瓶颈时一个经典的策略就是“空间换时间”。对于数组移动我们可以直接计算出每个元素移动后的最终位置。4.1 算法思路创建一个和原数组同样大小的临时数组temp。遍历原数组对于下标为i的元素它左移k位后的新下标是(i k) % n。但是这是“左移”吗仔细想想原数组下标i的元素左移k位后应该去往下标为(i - k n) % n的位置。更直观的做法是新数组中下标为j的元素应该来自原数组下标为(j k) % n的元素。因为新数组的第0个位置存放的是原数组第k个位置的元素左移k位的结果。将计算好的元素放入temp数组的对应位置。最后将temp数组的内容复制回原数组。4.2 代码实现void leftRotate(int arr[], int n, int k) { k k % n; if (k 0) return; // 移动位数为0直接返回 int temp[n]; // C99变长数组或者动态分配 int* temp (int*)malloc(n * sizeof(int)); // 将原数组元素放入新数组的正确位置 for (int i 0; i n; i) { temp[i] arr[(i k) % n]; // 注意这里的下标关系 } // 将结果复制回原数组 for (int i 0; i n; i) { arr[i] temp[i]; } // 如果使用了malloc记得 free(temp); }4.3 复杂度分析与权衡时间复杂度我们遍历了两次数组一次填充temp一次写回arr每次都是O(n)的线性遍历所以总时间复杂度是O(n)。这是一个巨大的提升无论k多大我们都只遍历固定次数。空间复杂度我们使用了一个大小为n的额外数组所以空间复杂度是O(n)。实操心得这是竞赛中最“稳”的一种写法。思路清晰不易出错代码简洁。在绝大多数情况下O(n)的额外空间是可以接受的尤其是题目没有明确禁止使用额外数组时。在时间紧迫的竞赛中优先实现这种解法确保拿到基础分是明智的选择。它的缺点就是需要额外的内存如果数组非常大例如上亿级别可能会成为问题但蓝桥杯常规题目的数据范围通常不会卡这一点。5. 解法三原地逆置法——算法艺术的体现有没有一种方法既能达到O(n)的时间复杂度又能像暴力法一样只使用O(1)的额外空间呢答案是肯定的这就是堪称经典的“三次逆置法”。它巧妙利用了数组逆置的特性充满了数学美感。5.1 算法原理与推导我们目标是左移k位。观察数组A [1,2,3,4,5,6,7], k2结果应为[3,4,5,6,7,1,2]。我们可以将数组分成两部分前k个元素X [1,2]和剩余元素Y [3,4,5,6,7]。左移k位的结果就是YX即[3,4,5,6,7,1,2]。神奇的事情发生了先将X逆置得到X [2,1]数组变为[2,1,3,4,5,6,7]。再将Y逆置得到Y [7,6,5,4,3]数组变为[2,1,7,6,5,4,3]。最后将整个数组逆置得到[3,4,5,6,7,1,2]。这正是我们想要的YX为什么这可以用数学公式来解释。设原数组为XY。操作1后XY操作2后XY操作3后(XY) (Y)(X) YX。这正是我们想要的结果。5.2 代码实现我们需要先实现一个反转数组某一部分的辅助函数。// 反转数组arr中从索引start到end包含的部分 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 leftRotate(int arr[], int n, int k) { k k % n; if (k 0) return; // 三步逆置 reverse(arr, 0, k - 1); // 逆置前k个元素 reverse(arr, k, n - 1); // 逆置剩余n-k个元素 reverse(arr, 0, n - 1); // 逆置整个数组 }代码简洁得令人惊叹整个核心逻辑只有三行。5.3 复杂度与优势分析时间复杂度三次reverse操作。reverse函数通过双指针遍历指定区间时间复杂度是区间长度。三次操作的总长度分别是k、(n-k)、n加起来是2n。所以总时间复杂度依然是O(n)。空间复杂度只使用了常数级别的额外空间temp变量和几个索引是O(1)。踩坑提醒实现reverse函数时循环条件while (start end)是关键。如果写成当区间长度为奇数时中间元素会被自己交换虽然结果可能也对但多了一次无谓操作更严重的是如果start和end在某种情况下相等会导致错误的交换。坚持使用是最安全清晰的。6. 解法四环状替换法——另一种原地O(n)的巧妙思路除了逆置法还有一种同样能达到O(n)时间、O(1)空间的算法称为“环状替换”或“约瑟夫环式替换”。它的思想更加直接把数组想象成一个个环我们沿着环把元素放到它最终的位置上。6.1 算法思路我们从数组的起始位置索引0开始。这个位置的元素最终应该去往索引(0 - k n) % n的位置记为next。我们把arr[0]的值暂存到temp然后把arr[next]的值放到arr[0]吗不对这样会覆盖。正确的做法是我们想把arr[0]放到arr[next]但需要先把arr[next]的元素挪走。所以我们实际上是在沿着一个环依次替换元素。更系统的步骤是从索引i 0开始保存其值temp arr[i]。它的目标位置是j (i - k n) % n。但是我们选择正向思考我们将arr[i]的值放到它左移k位后的新位置new_i (i k) % n这又回到了辅助数组的思路。环状替换的精髓是一次完成整个环的移动。实际上标准的环状替换算法是处理右移更直观。对于左移k位等价于右移n-k位。我们以右移r n - k位来阐述。我们从索引0开始把arr[0]移动到arr[r]但需要先把arr[r]移走。我们把arr[r]移动到arr[(rr)%n]... 如此继续直到回到起点。这可能会形成多个环。6.2 代码实现与过程模拟以数组[1,2,3,4,5,6,7], 左移k2位为例。这等价于右移r5位。 我们从索引0开始temp arr[0] 1。它应该去的位置是 (05)%75。我们把 arr[5]6 移到 arr[0]不对我们应该把1放到5但5的位置现在是6。所以正确的流程是我们打算把1放到5但需要先处理5位置上的元素6。所以我们记录1然后去看位置5。 这个过程描述起来复杂直接看实现代码它通过计算最大公约数(GCD)来确定环的个数// 计算最大公约数 int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } void leftRotate(int arr[], int n, int k) { k k % n; if (k 0) return; int r n - k; // 将左移k位转化为右移r位来处理 int cycles gcd(n, r); // 环的个数等于n和r的最大公约数 for (int i 0; i cycles; i) { int temp arr[i]; int j i; while (1) { int next (j r) % n; // 计算j位置元素应该去往的位置 if (next i) { // 如果回到了环的起点 arr[j] temp; break; } arr[j] arr[next]; // 把下一个位置的元素拿过来 j next; // 移动到下一个位置 } } }以n7, r5为例gcd(7,5)1只有一个环。从i0开始temparr[0]1, j0。next(05)%75。next ! i所以 arr[0] arr[5] (6)。数组变[6,2,3,4,5,6,7]。j5。next(55)%73。arr[5] arr[3] (4)。数组变[6,2,3,4,5,4,7]。j3。next(35)%71。arr[3] arr[1] (2)。数组变[6,2,3,2,5,4,7]。j1。next(15)%76。arr[1] arr[6] (7)。数组变[6,7,3,2,5,4,7]。j6。next(65)%74。arr[6] arr[4] (5)。数组变[6,7,3,2,5,4,5]。j4。next(45)%72。arr[4] arr[2] (3)。数组变[6,7,3,2,3,4,5]。j2。next(25)%70。next i (0)。所以 arr[2] temp (1)。数组最终为[6,7,1,2,3,4,5]。等等这看起来不对我们得到了右移5位即左移2位的结果[6,7,1,2,3,4,5]检查一下原数组[1,2,3,4,5,6,7]左移2位应该是[3,4,5,6,7,1,2]。我们得到的是[6,7,1,2,3,4,5]这实际上是右移了1位。这里出现了偏差说明环状替换算法的下标处理需要非常小心很容易绕晕。实际上更常见的环状替换算法直接处理左移但需要处理多个环的情况。一个更清晰且正确的左移环状替换实现如下int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } void leftRotate(int arr[], int n, int k) { k k % n; int cycles gcd(n, k); // 环的个数 for (int i 0; i cycles; i) { int temp arr[i]; int j i; while (1) { int next (j k) % n; // 注意这里是 k计算左移k位后的位置 if (next i) { arr[j] temp; break; } arr[j] arr[next]; j next; } } }这个算法是正确的。它的核心思想是元素从位置j左移k位后会去到位置(jk)%n。我们从每个环的起点开始用temp保存起点值然后把后面元素依次前移填充空位最后把temp填到环的最后一个位置。环的个数由n和k的最大公约数决定这保证了所有元素都被移动且只移动一次。6.3 复杂度与适用性时间复杂度每个元素都被访问和移动了一次所以是O(n)。空间复杂度O(1)。重要提示环状替换法虽然高效但逻辑非常绕极易出错。在紧张的竞赛环境中除非你对其原理烂熟于心否则不建议首选。三次逆置法在达到同样效率O(n)时间O(1)空间的前提下思路和代码都清晰得多是更优的“炫技”选择。7. 实战测试与不同场景下的选择策略纸上得来终觉浅绝知此事要躬行。我们设计几个测试用例来验证上述算法的正确性并讨论在什么情况下该选择哪种解法。7.1 测试用例设计全面的测试应该覆盖以下边界和常规情况常规情况arr [1,2,3,4,5,6,7], k2。预期输出[3,4,5,6,7,1,2]。k0arr [1,2,3,4,5], k0。预期数组不变。k等于数组长度narr [1,2,3], k3。移动后数组应不变[1,2,3]。k大于数组长度narr [1,2,3,4], k6。有效移动为k%n2预期输出[3,4,1,2]。单元素数组arr [5], k10。无论如何移动结果都是[5]。空数组arr [], k5。函数应该能处理n0的情况避免除零错误。我们可以编写一个简单的测试程序来验证#include stdio.h #include string.h // 用于memcmp比较数组 // 这里插入你选择的leftRotate函数实现例如三次逆置法 void reverse(int arr[], int start, int end) { /* ... */ } void leftRotate(int arr[], int n, int k) { /* ... */ } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { // 测试用例1 int arr1[] {1,2,3,4,5,6,7}; int n1 7, k1 2; int expected1[] {3,4,5,6,7,1,2}; leftRotate(arr1, n1, k1); printf(Test 1: %s\n, memcmp(arr1, expected1, n1*sizeof(int)) 0 ? PASS : FAIL); printArray(arr1, n1); // 测试用例4: k n int arr4[] {1,2,3,4}; int n4 4, k4 6; int expected4[] {3,4,1,2}; leftRotate(arr4, n4, k4); printf(Test 4 (kn): %s\n, memcmp(arr4, expected4, n4*sizeof(int)) 0 ? PASS : FAIL); printArray(arr4, n4); // 测试用例5: 单元素 int arr5[] {5}; int n5 1, k5 10; int expected5[] {5}; leftRotate(arr5, n5, k5); printf(Test 5 (single element): %s\n, memcmp(arr5, expected5, n5*sizeof(int)) 0 ? PASS : FAIL); printArray(arr5, n5); return 0; }7.2 如何根据场景选择算法追求快速AC竞赛场景首选辅助数组法。思路直白代码简单不易出错时间复杂度O(n)在竞赛数据范围内完全够用。在时间有限的比赛中可靠性是第一位的。追求极致空间效率嵌入式或内存严格受限环境选择三次逆置法。它满足了O(n)时间和O(1)空间的双重要求代码也相对优雅是体现算法功力的不二之选。教学或理解原理从暴力法开始理解移动的本质。然后学习辅助数组法理解空间换时间。最后研究三次逆置法和环状替换法领略算法的巧妙。应对面试面试官很可能希望你给出多种解法并分析其优劣。你应该能够流畅地讲出暴力法、辅助数组法和三次逆置法如果能提到环状替换法的思想就更好了。重点要清晰地说出时间复杂度和空间复杂度以及各自的适用场景。个人经验在真正的蓝桥杯赛场上除非题目有明确的“请使用O(1)额外空间”的要求否则我强烈建议使用辅助数组法。它的代码几乎就是“思维的直接翻译”在高压环境下能最大程度减少调试时间。把省下来的时间留给后面更复杂的题目是更划算的策略。三次逆置法可以作为检查时的备选或者时间充裕时的优化。8. 举一反三数组移动问题的变体与扩展掌握了基础的循环左移我们就可以应对一系列相关的变体问题。这些问题考察的是对同一核心思想的应用和迁移能力。8.1 循环右移循环右移k位可以转化为循环左移n-k位。当然也可以直接实现“三次逆置法”的右移版本先逆置整个数组再逆置前k个元素最后逆置剩余n-k个元素。代码只需调整reverse的调用顺序void rightRotate(int arr[], int n, int k) { k k % n; if (k 0) return; // 右移k位逆置整个数组 - 逆置前k个 - 逆置剩余部分 reverse(arr, 0, n - 1); reverse(arr, 0, k - 1); reverse(arr, k, n - 1); }8.2 数组部分区间移动题目可能要求只对数组的某个子区间[L, R]进行循环左移。思路可以借鉴辅助数组法将这个子区间复制到临时数组移动后再复制回去。逆置法同样适用。对子区间[L, R]移动k位可以逆置[L, Lk-1]逆置[Lk, R]逆置[L, R]8.3 双指针法与数组“移动”有一类问题如“移动零”LeetCode 283要求将数组中的所有0移动到末尾同时保持非零元素的相对顺序。这虽然不是循环移动但也是“移动”操作。这类问题通常使用双指针技巧一个指针i遍历数组另一个指针j指向下一个非零元素应该存放的位置。这提供了另一种“移动”的思维模式通过覆盖和交换来重新排列而不是开辟新空间。void moveZeroes(int* nums, int numsSize){ int j 0; // j指向下一个非零元素该放的位置 for (int i 0; i numsSize; i) { if (nums[i] ! 0) { // 交换nums[i]和nums[j] int temp nums[i]; nums[i] nums[j]; nums[j] temp; j; } } }8.4 多维数组的“移动”在蓝桥杯或一些应用中可能会遇到二维数组矩阵的行循环移动或列循环移动。其核心思想是降维处理。例如将矩阵的每一行看成一个一维数组分别调用一维数组的循环移动函数即可。列移动则需要更小心的下标计算或者先将矩阵转置行移动后再转置回来。通过ALGO-970“数组移动”这道题我们深入探讨了从暴力模拟到空间换时间再到巧妙的原地逆置和环状替换等多种解法。在算法学习和竞赛中这种对基础操作的深度挖掘至关重要。它锻炼的不仅仅是写出代码的能力更是分析问题、比较方案、选择最优策略的思维能力。下次再遇到“移动”、“旋转”、“重排”这类关键词时希望你的思路能像我们今天梳理的一样清晰。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
