【普通数组】LC 189.轮转数组

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析法1三次翻转法法2环状替换法法3额外数组映射2、解题代码法1三次翻转法法2环状替换法法3额外数组映射三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接189.轮转数组2、题目描述二、个人思路整理1、思路分析法1三次翻转法向右轮转k kk位本质上是将数组末尾的k kk个元素搬到数组头部其余元素整体右移。通过三次局部/全局翻转可以直接在原地达成目标。算法步骤翻转整个数组使原本末尾的k kk个元素移到前半部分但顺序是反的前半部分的元素移到后半部分顺序也是反的。翻转前k kk个元素恢复前半部分元素的相对顺序。翻转后n − k n - kn−k个元素恢复后半部分元素的相对顺序。以nums [1, 2, 3, 4, 5, 6, 7],k 3为例翻转全部[7, 6, 5, 4, 3, 2, 1]翻转前k kk个 (索引区间[0, 2]):[5, 6, 7, 4, 3, 2, 1]翻转后n − k n-kn−k个 (索引区间[3, 6]):[5, 6, 7, 1, 2, 3, 4]法2环状替换法每个位置i ii的元素最终都会去往( i k ) ( m o d n ) (i k) \pmod n(ik)(modn)。如果将所有位置看作一个置换群可以从位置0 00出发依次将元素放入目标位置直到回到起点形成一个环。当数组长度n nn与k kk的最大公约数gcd ⁡ ( n , k ) d 1 \gcd(n, k) d 1gcd(n,k)d1时会形成d dd个互不重叠的环因此需要从索引0 00到d − 1 d-1d−1分别遍历每个环。法3额外数组映射开辟一个与原数组大小相同的新数组直接利用公式new_nums[(i k) % n] nums[i]赋值最后将新数组拷贝回原数组。2、解题代码法1三次翻转法classSolution{public:voidrotate(vectorintnums,intk){intnnums.size();// 轮转n次相当于没动取模消除整轮移动k%n;// 若k为0数组无须任何变动if(k0){return;}// 1. 翻转整个数组把末尾 k 个元素移动到数组前半部分此时顺序是逆序的reverse(nums.begin(),nums.end());// 2. 翻转前 k 个元素 [0, k - 1]恢复前半部分元素的正序reverse(nums.begin(),nums.begin()k);// 3. 翻转后 n - k 个元素 [k, n - 1]恢复后半部分元素的正序reverse(nums.begin()k,nums.end());}};复杂度分析时间复杂度O ( n ) O(n)O(n)每个元素最多被访问/交换 2 次。空间复杂度O ( 1 ) O(1)O(1)一个int变量空间原地操作。法2环状替换法classSolution{public:voidrotate(vectorintnums,intk){intnnums.size();k%n;if(k0){return;}// 记录已经就位的元素总数全部处理完后退出intcount0;// 当gcd(n, k) 1时会存在多个独立的闭环需要遍历不同起点for(intstart0;countn;start){intcurrentstart;// 当前要放置的起始索引intprev_valnums[start];// 待放入目标位置的值// 沿置换环依次向前传递并覆盖元素直到回到起始索引do{intnext_idx(currentk)%n;// 计算目标位置inttempnums[next_idx];// 暂存被覆盖的值nums[next_idx]prev_val;// 将值放入目标位置prev_valtemp;// 更新待放置的值currentnext_idx;// 移动到下一个目标位置count;// 就位元素加1}while(start!current);// 回到环的起点时结束本轮}}};复杂度分析时间复杂度O ( n ) O(n)O(n)每个元素恰好移动一次。空间复杂度O ( 1 ) O(1)O(1)若干int变量空间原地操作。法3额外数组映射classSolution{public:voidrotate(vectorintnums,intk){intnnums.size();vectorinttemp(n);for(inti0;inums.size();i){temp[(ik)%n]nums[i];}numstemp;}};复杂度分析时间复杂度O ( n ) O(n)O(n)单层for循环。空间复杂度O ( n ) O(n)O(n)一维数组辅助空间。三、知识风暴数组轮转是数组类问题中的经典操作其核心在于原地修改与元素移动的平衡。本文的三种解法分别从「整体翻转」「置换环」「空间换时间」三个角度切入理解它们有助于应对更多数组变形类题目。算法核心思想取模化简轮转k kk位等价于轮转k m o d n k \bmod nkmodn位先取模可消除整轮无效移动。三次翻转先整体翻转再分别翻转前后两段即可在O ( 1 ) O(1)O(1)额外空间内完成轮转是「原地算法」的经典范式。环状替换每个元素最终去往( i k ) m o d n (i k) \bmod n(ik)modn沿置换环依次传递覆盖每个元素恰好移动一次。额外数组映射直接利用new_nums[(i k) % n] nums[i]映射思路最直观但需要O ( n ) O(n)O(n)辅助空间。算法变体与扩展向左轮转将「向右轮转k kk位」改为「向左轮转k kk位」只需把翻转区间从[0, k-1]与[k, n-1]调整为[0, n-k-1]与[n-k, n-1]。轮转二维数组矩阵旋转如 LeetCode 48「旋转图像」本质是矩阵的轮转可拆解为「转置 行翻转」两步完成。查询多次轮转结果若需频繁查询不同k kk的轮转结果可先复制一份数组拼接成2n长度用滑动窗口O ( 1 ) O(1)O(1)回答每次查询。部分轮转区间轮转只对数组中某个子区间做轮转可结合「差分 三次翻转」在子区间上局部完成。与其他算法的对比三次翻转法O ( n ) O(n)O(n)时间、O ( 1 ) O(1)O(1)空间代码最简洁是面试首选。环状替换法O ( n ) O(n)O(n)时间、O ( 1 ) O(1)O(1)空间但需处理gcd ⁡ ( n , k ) \gcd(n, k)gcd(n,k)个独立环边界较易出错。额外数组映射O ( n ) O(n)O(n)时间、O ( n ) O(n)O(n)空间思路最直观适合快速实现或作为正确性参照。相关 LeetCode 例题189. 轮转数组本题48. 旋转图像二维矩阵轮转转置 翻转61. 旋转链表链表轮转先成环再断开396. 旋转函数轮转后求最大值递推优化