189. 轮转数组题目链接题目描述给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。示例 1:输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]解题思路关键点注意处理k可能大于数组长度的情况需要使用取模运算需要原地修改数组不能使用额外的数组虽然方法1和方法2用了额外空间但题目要求O(1)空间三种解法对比方法一双倍数组法voidrotate(vectorintnums,intk){intnnums.size();kk%n;// 处理k大于n的情况vectorintnums1(nums);// 复制原数组nums1.insert(nums1.end(),nums.begin(),nums.end());// 拼接两份nums.clear();nums.insert(nums.begin(),nums1.begin()n-k,nums1.begin()2*n-k);}思路解析先把原数组复制一份然后拼接到自己后面从新数组的n-k位置开始取n个元素用这个子数组替换原数组示例nums [1,2,3,4,5], k2, n5 nums1 [1,2,3,4,5,1,2,3,4,5] 从位置 n-k3 开始取5个nums1[3]4, [4]5, [5]1, [6]2, [7]3 结果[4,5,1,2,3]复杂度时间复杂度O(n)需要遍历数组空间复杂度O(n)需要额外的数组空间方法二额外数组法voidrotate(vectorintnums,intk){intnnums.size();vectorintnums1(n);for(inti0;in;i){nums1[(ik)%n]nums[i];}nums.assign(nums1.begin(),nums1.end());}思路解析创建一个和原数组同样大小的新数组遍历原数组将每个元素放到新数组的(ik)%n位置用新数组替换原数组示例nums [1,2,3,4,5], k2, n5 i0: nums1[(02)%52] 1 → nums1[2]1 i1: nums1[(12)%53] 2 → nums1[3]2 i2: nums1[(22)%54] 3 → nums1[4]3 i3: nums1[(32)%50] 4 → nums1[0]4 i4: nums1[(42)%51] 5 → nums1[1]5 nums1 [4,5,1,2,3]复杂度时间复杂度O(n)需要遍历数组空间复杂度O(n)需要额外的数组空间方法三三次反转法最优解voidrotate(vectorintnums,intk){intnnums.size();kk%n;reverse(nums.begin(),nums.end());// 反转整个数组reverse(nums.begin(),nums.begin()k);// 反转前k个reverse(nums.begin()k,nums.end());// 反转剩下的}思路解析先反转整个数组再反转前k个元素最后反转剩下的n-k个元素示例nums [1,2,3,4,5], k2, n5 1. 整体反转: [5,4,3,2,1] 2. 反转前k2个: [4,5,3,2,1] 3. 反转剩下的n-k3个: [4,5,1,2,3]数学原理向右旋转k位相当于把后k个元素移到前面。通过三次反转可以巧妙地实现这个操作整体反转把末尾元素放到开头反转前k个恢复被反转的尾部顺序反转剩下的恢复被反转的头部顺序复杂度时间复杂度O(n)三次反转操作空间复杂度O(1)原地修改不需要额外空间总结对比方法时间复杂度空间复杂度优点缺点双倍数组法O(n)O(n)思路直观容易理解需要额外O(n)空间额外数组法O(n)O(n)逻辑简单清晰需要额外O(n)空间三次反转法O(n)O(1)最优解原地修改需要理解反转原理注意事项必须处理k n的情况通过k k % n取模题目要求原地修改但有些方法用了额外空间三种方法都要掌握但面试时尽量用第三种