LeetCode 189.轮转数组 | 从暴力到 O(n)O(1) 最优解法全程解析一、题目简介题目给定一个数组将数组中的元素向右轮转 k 个位置其中 k 是非负数。示例nums [1,2,3,4,5,6,7], k 3轮转结果[5,6,7,1,2,3,4]这道题是数组经典高频题非常适合新手理解算法优化思维。题目看似简单但包含三种完全不同的解题思路从暴力模拟、空间换时间到面试最优的三次反转原地算法层层递进可以完整吃透数组操作思想。题目隐含细节k 可能大于数组长度数组轮转 n 次后会还原所以所有解法都需要先取模k k % numsSize。二、解法一暴力模拟 — 一步步右旋直观易懂1. 思路分析最朴素的思路右旋 k 位那就循环 k 次每次整体右移一位。单次右移逻辑Save the last element of the array前面所有元素统一向后挪一位把末尾元素放到数组头部重复 k 次即可完成整体轮转。2. 完整代码voidrotate(int*nums,intnumsSize,intk){kk%numsSize;while(k--){inttmpnums[numsSize-1];for(intinumsSize-2;i0;i--){nums[i1]nums[i];}nums[0]tmp;}}3. 复杂度分析时间复杂度O(n²)每一轮移动需要遍历整个数组最多执行 n 轮嵌套循环空间复杂度O(1)仅使用临时变量原地修改数组4. 优缺点总结✅ 优点逻辑极其直观完全模拟手动操作新手极易理解❌ 缺点效率极低数据量大时会超时仅适合学习思路不适合工程使用三、解法二辅助数组 — 空间换时间线性时间最优1. 思路分析暴力算法慢的核心原因大量重复移动元素。我们可以直接开辟一个新数组通过数学映射直接定位每个元素的最终位置一步到位。核心公式new[(i k) % n] nums[i]含义原数组下标为 i 的元素向右移动 k 位后会落在新数组下标(ik)%n的位置。取模是为了实现数组环形轮转。2. 完整代码voidrotate(int*nums,intnumsSize,intk){intnews[numsSize];kk%numsSize;for(inti0;inumsSize;i){news[(ik)%numsSize]nums[i];}// 拷贝回原数组for(inti0;inumsSize;i){nums[i]news[i];}}3. 复杂度分析时间复杂度O(n)仅两次线性遍历数组无嵌套循环空间复杂度O(n)开辟了和原数组等大的辅助数组4. 优缺点总结✅ 优点代码简洁、时间效率最高、零思维压力❌ 缺点占用额外空间不满足「原地修改数组」的进阶要求四、解法三三次反转 — 面试最优原地算法O(n) O(1)前面两种解法各有短板暴力时间差、辅助数组空间差。三次反转法可以同时做到线性时间 原地常数空间是面试标准答案。1. 核心原理数组右旋 k 位可以拆解为三段简单的反转操作反转前n-k个元素反转后k个元素整体反转整个数组以[1,2,3,4,5,6,7],k3举例推演原数组1 2 3 4 | 5 6 7反转前4个4 3 2 1 | 5 6 7反转后3个4 3 2 1 | 7 6 5整体反转5 6 7 1 2 3 4最终结果正确2. 完整代码// 区间反转函数voidreverse(int*nums,intleft,intright){while(leftright){inttmpnums[left];nums[left]nums[right];nums[right]tmp;left;right--;}}voidrotate(int*nums,intnumsSize,intk){kk%numsSize;reverse(nums,0,numsSize-k-1);// 反转前 n-k 个reverse(nums,numsSize-k,numsSize-1);// 反转后 k 个reverse(nums,0,numsSize-1);// 整体反转}3. 复杂度分析时间复杂度O(n)所有元素仅被反转遍历常数次总次数为线性级别空间复杂度O(1)全程原地交换无额外数组开销4. 优缺点总结✅ 优点时间、空间双最优原地算法面试满分解法❌ 缺点无法直观脑补需要理解分段反转规律五、三种解法终极对比解法时间复杂度空间复杂度原地修改适用场景暴力逐轮移动O(n²)O(1)是新手入门理解逻辑辅助数组法O(n)O(n)否追求代码简单、不限制空间三次反转法O(n)O(1)是面试、工程最优解六、高频易错点总结忘记取模 k%n当 k 大于数组长度时直接报错所有解法必须预处理反转区间下标写错前 n-k 个的右端点是numsSize-k-1极易写错位左右旋混淆本文是右旋模板左旋需要调换反转顺序变长数组兼容性C 语言中int news[n]是 C99 特性老旧编译器不支持七、思维总结这道题的优化路径是算法学习最经典的成长路径纯模拟暴力 → 空间换时间 → 找规律极致优化很多新手觉得“会做题就行”但真正的算法能力是不断抛弃暴力、寻找数学规律、用最低开销解决问题。三次反转的思想不仅适用于轮转数组还可以迁移到字符串反转、字符串轮转、区间翻转等大量题目是非常通用的数组解题技巧。