LeetCode 189数组轮转问题详解辅助数组法与三次翻转法前言在数组相关面试题中LeetCode 189《轮转数组》是一道非常经典的题目。题目要求将数组中的元素整体向右移动 k 个位置并且直接修改原数组。看似只是简单的数据移动但实际上涉及索引映射、取模运算以及原地算法等知识点。本文将详细介绍两种常见解法辅助数组法容易理解三次翻转法面试高频并分析两种方案的优缺点和适用场景。一、题目描述给定一个整数数组 nums将数组中的元素向右轮转 k 个位置。示例输入 nums[1,2,3,4,5,6,7]k3输出[5,6,7,1,2,3,4]可以理解为原数组 1 2 3 4 5 6 7 向右移动3位 5 6 7 1 2 3 4方法一辅助数组法思路分析对于数组中的每一个元素都可以直接计算出它轮转后的新位置。假设数组长度为 n当前元素下标为 i向右移动 k 位则新的下标为(ik)%n这里的%用于处理越界情况。例如nums[1,2,3,4,5]k2原下标新下标0213243041最终结果[4,5,1,2,3]代码实现fromtypingimportListclassSolution:defrotate(self,nums:List[int],k:int)-None:nlen(nums)k%n new_nums[0]*nforiinrange(n):new_nums[(ik)%n]nums[i]foriinrange(n):nums[i]new_nums[i]图解过程原数组 1 2 3 4 5 6 7 0 1 2 3 4 5 6 k 3元素移动1 → 下标3 2 → 下标4 3 → 下标5 4 → 下标6 5 → 下标0 6 → 下标1 7 → 下标2得到5 6 7 1 2 3 4复杂度分析时间复杂度O(n)空间复杂度O(n)因为额外申请了一个与原数组等长的辅助数组。优缺点优点思路直观最容易写对适合刷题入门缺点需要额外 O(n) 空间方法二三次翻转法为什么想到翻转观察下面这个例子[1,2,3,4,5,6,7]向右移动3位[5,6,7,1,2,3,4]实际上可以看成前半部分 1 2 3 4 后半部分 5 6 7把后半部分移动到前面即可。问题在于如何原地完成。核心技巧通过三次翻转实现。第一次翻转整个数组1 2 3 4 5 6 7 ↓ 7 6 5 4 3 2 1第二次翻转前 k 个元素k 37 6 5 | 4 3 2 1 ↓ 5 6 7 | 4 3 2 1第三次翻转剩余元素5 6 7 | 4 3 2 1 ↓ 5 6 7 | 1 2 3 4最终结果5 6 7 1 2 3 4成功完成轮转。代码实现fromtypingimportListclassSolution:defrotate(self,nums:List[int],k:int)-None:nlen(nums)k%ndefreverse(left,right):whileleftright:nums[left],nums[right]nums[right],nums[left]left1right-1reverse(0,n-1)reverse(0,k-1)reverse(k,n-1)复杂度分析时间复杂度O(n)虽然执行了三次翻转但每个元素仅被访问常数次。空间复杂度O(1)只使用了有限个辅助变量。为什么三次翻转一定正确第一次翻转后A B ↓ B反 A反其中A 前 n-k 个元素 B 后 k 个元素第二次翻转B反 → B第三次翻转A反 → A最终得到B A这正是向右轮转 k 位后的结果。两种方案对比方案时间复杂度空间复杂度推荐程度辅助数组法O(n)O(n)★★★★★三次翻转法O(n)O(1)★★★★★面试如何回答如果面试官问如何实现数组右旋 k 位建议按照下面顺序回答第一步先说最容易想到的辅助数组法。利用 (ik)%n 计算元素的新位置 时间 O(n)空间 O(n)。第二步进一步优化空间。利用三次翻转 整体翻转 → 翻转前k个 → 翻转后n-k个 时间 O(n) 空间 O(1)这样能体现你不仅会做题还具备优化思维。总结轮转数组本质上是一个下标映射问题。辅助数组法利用(ik)%n直接计算元素的新位置实现简单、容易理解。三次翻转法则利用数组翻转的性质在不申请额外空间的情况下完成轮转是这道题最经典、最常考的解法。刷题阶段建议先掌握辅助数组法理解轮转规律面试阶段重点掌握三次翻转法这是面试官最希望看到的解法。