企业官网建设流程全解析

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 次，每次整体右移一位。

单次右移逻辑：

1. Save the last element of the array
2. 前面所有元素统一向后挪一位
3. 把末尾元素放到数组头部

重复 k 次，即可完成整体轮转。

2. 完整代码

voidrotate(int*nums,intnumsSize,intk){k=k%numsSize;while(k--){inttmp=nums[numsSize-1];for(inti=numsSize-2;i>=0;i--){nums[i+1]=nums[i];}nums[0]=tmp;}}

3. 复杂度分析

• 时间复杂度：O(n²)，每一轮移动需要遍历整个数组，最多执行 n 轮，嵌套循环
• 空间复杂度：O(1)，仅使用临时变量，原地修改数组

4. 优缺点总结

✅ 优点：逻辑极其直观，完全模拟手动操作，新手极易理解
❌ 缺点：效率极低，数据量大时会超时，仅适合学习思路，不适合工程使用

三、解法二：辅助数组 — 空间换时间（线性时间最优）

1. 思路分析

暴力算法慢的核心原因：大量重复移动元素。

我们可以直接开辟一个新数组，通过数学映射直接定位每个元素的最终位置，一步到位。

核心公式：new[(i + k) % n] = nums[i]
含义：原数组下标为 i 的元素，向右移动 k 位后，会落在新数组下标(i+k)%n的位置。取模是为了实现数组环形轮转。

2. 完整代码

voidrotate(int*nums,intnumsSize,intk){intnews[numsSize];k=k%numsSize;for(inti=0;i<numsSize;i++){news[(i+k)%numsSize]=nums[i];}// 拷贝回原数组for(inti=0;i<numsSize;i++){nums[i]=news[i];}}

3. 复杂度分析

• 时间复杂度：O(n)，仅两次线性遍历数组，无嵌套循环
• 空间复杂度：O(n)，开辟了和原数组等大的辅助数组

4. 优缺点总结

✅ 优点：代码简洁、时间效率最高、零思维压力
❌ 缺点：占用额外空间，不满足「原地修改数组」的进阶要求

四、解法三：三次反转 — 面试最优原地算法（O(n) + O(1)）

前面两种解法各有短板：暴力时间差、辅助数组空间差。三次反转法可以同时做到线性时间 + 原地常数空间，是面试标准答案。

1. 核心原理

数组右旋 k 位，可以拆解为三段简单的反转操作：

1. 反转前n-k个元素
2. 反转后k个元素
3. 整体反转整个数组

以[1,2,3,4,5,6,7],k=3举例推演：

• 原数组：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(left<right){inttmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}}voidrotate(int*nums,intnumsSize,intk){k=k%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. 优缺点总结

✅ 优点：时间、空间双最优，原地算法，面试满分解法
❌ 缺点：无法直观脑补，需要理解分段反转规律

五、三种解法终极对比

六、高频易错点总结

1. 忘记取模 k%n：当 k 大于数组长度时直接报错，所有解法必须预处理
2. 反转区间下标写错：前 n-k 个的右端点是numsSize-k-1，极易写错位
3. 左右旋混淆：本文是右旋模板，左旋需要调换反转顺序
4. 变长数组兼容性：C 语言中int news[n]是 C99 特性，老旧编译器不支持

七、思维总结

这道题的优化路径，是算法学习最经典的成长路径：
纯模拟暴力 → 空间换时间 → 找规律极致优化

很多新手觉得“会做题就行”，但真正的算法能力，是不断抛弃暴力、寻找数学规律、用最低开销解决问题。

三次反转的思想不仅适用于轮转数组，还可以迁移到字符串反转、字符串轮转、区间翻转等大量题目，是非常通用的数组解题技巧。