【力扣100题】58.轮转数组

题目描述给定一个整数数组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] 示例 2 输入nums [-1,-100,3,99], k 2 输出[3,99,-1,-100] 解释 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]提示1 nums.length 10^5-2^31 nums[i] 2^31 - 10 k 10^5解题思路总览方法核心思想时间复杂度空间复杂度备注三次翻转先整体翻转再分别翻转两段O(n)O(1)推荐解法最优环状替换每个元素放到最终位置O(n)O(1)需要处理 gcd暴力法每次轮转一个元素O(n*k)O(1)会超时额外数组借助临时数组O(n)O(n)最简单但空间不优一、三次翻转法最常用核心思想通过三次反转操作将数组向右轮转 k 位原数组: [1,2,3,4,5,6,7], k 3 第一步整体翻转 reverse(nums, 0, n-1) [7,6,5,4,3,2,1] 第二步翻转前 k 个元素 reverse(nums, 0, k-1) [5,6,7,4,3,2,1] 第三步翻转后 n-k 个元素 reverse(nums, k, n-1) [5,6,7,1,2,3,4] 结果[5,6,7,1,2,3,4]图解nums [1,2,3,4,5,6,7], k 3 初始状态: [1, 2, 3, 4, 5, 6, 7] 0 1 2 3 4 5 6 第一步reverse(0, 6) [7, 6, 5, 4, 3, 2, 1] 第二步reverse(0, 2) [5, 6, 7, 4, 3, 2, 1] 第三步reverse(3, 6) [5, 6, 7, 1, 2, 3, 4] 输出: [5,6,7,1,2,3,4]代码实现classSolution{public:voidrotate(vectorintnums,intk){k%nums.size();// 取模防止 k 大于数组长度ranges::reverse(nums);// 整体翻转 [1,2,3,4,5,6,7] - [7,6,5,4,3,2,1]reverse(nums.begin(),nums.begin()k);// 翻转前 k 个 [7,6,5] - [5,6,7]reverse(nums.begin()k,nums.end());// 翻转后 n-k 个 [4,3,2,1] - [1,2,3,4]}};二、算法流程图详细过程以 nums [1,2,3,4,5,6,7], k 3 为例输入: nums [1,2,3,4,5,6,7], k 3 Step 1: k % n n 7, k 3 % 7 3 Step 2: ranges::reverse(nums) 翻转整个数组 [1,2,3,4,5,6,7] - [7,6,5,4,3,2,1] Step 3: reverse(nums.begin(), nums.begin()k) 翻转前 3 个元素 [7,6,5] [7,6,5,4,3,2,1] - [5,6,7,4,3,2,1] Step 4: reverse(nums.begin()k, nums.end()) 翻转后 4 个元素 [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]边界情况处理情况 1: k 0 k % n 0 整体翻转 翻转前 0 个 翻转后 n 个 整体翻转再整体翻转 不变 结果正确 情况 2: k n数组长度 k % n 0 相当于没有轮转 结果正确 情况 3: k n 例如 n7, k10 k % n 3 等价于轮转 3 位 结果正确三、逐行解析k%nums.size();取模防止 k 大于数组长度例如 n7, k10k % 7 3等价于轮转 3 位当 k 0 或 k n 时结果和原数组一样ranges::reverse(nums);C20 的ranges::reverse整体翻转数组[1,2,3,4,5,6,7]-[7,6,5,4,3,2,1]也可以用reverse(nums.begin(), nums.end())reverse(nums.begin(),nums.begin()k);翻转前 k 个元素[7,6,5,4,3,2,1]-[5,6,7,4,3,2,1]此时前 k 位已经在正确位置reverse(nums.begin()k,nums.end());翻转后 n-k 个元素[5,6,7,4,3,2,1]-[5,6,7,1,2,3,4]完成所有调整四、为什么三次翻转能实现轮转数学证明设数组长度为 n轮转 k 位。 整体翻转后原数组 [0...n-1] 变为 [n-1...0] 前 k 位翻转[n-1...n-k] 变为 [n-k...n-1] 后 n-k 位翻转[n-k-1...0] 变为 [n-k...n-1...0] 最终结果[n-k...n-1] [0...n-k-1] 轮转后的正确顺序 证毕。直观理解原始数组: [1,2,3,4,5,6,7] 目标: [5,6,7,1,2,3,4] 后k位 前n-k位 观察 - 后 k 位 [5,6,7] 在原数组中是前 n-k 位 - 前 n-k 位 [1,2,3,4] 在原数组中是后 n-k 位 三次翻转的作用 1. 整体翻转 - 把顺序反过来 2. 翻转前 k - 把后 k 位翻到前面但顺序反了 3. 翻转后 n-k - 把前 n-k 位翻到后面顺序也反了 两个反了抵消最终得到正确顺序。五、环状替换法核心思想每个元素直接放到最终位置通过换手处理。nums [1,2,3,4,5,6,7], k 3 数组下标对应关系 原位置 0 - 新位置 (0k) % n 3 原位置 1 - 新位置 (1k) % n 4 原位置 2 - 新位置 (5) % n 5 原位置 3 - 新位置 (6) % n 6 原位置 4 - 新位置 (0) % n 0 (回到起点) 原位置 5 - 新位置 (1) % n 1 原位置 6 - 新位置 (2) % n 2 从位置 0 开始顺时针走 0 - 3 - 6 - 2 - 5 - 1 - 4 - 0 形成一个环共 7 个元素classSolution{public:voidrotate(vectorintnums,intk){k%nums.size();intnnums.size();intcount0;// 已放置的元素个数for(intstart0;countn;start){intcurrstart;intprevnums[start];do{intnext(currk)%n;inttempnums[next];nums[next]prev;prevtemp;currnext;count;}while(curr!start);count;// 补偿最后一次多减的}}};与三次翻转法对比维度三次翻转环状替换代码复杂度简单3行搞定复杂需要处理环空间复杂度O(1)O(1)时间复杂度O(n)O(n)边界处理自动处理需要处理 gcd 防止死循环六、复杂度分析方法时间复杂度空间复杂度备注三次翻转O(n)O(1)推荐最简单环状替换O(n)O(1)需要小心处理暴力法O(n*k)O(1)会超时额外数组O(n)O(n)最简单但空间不优详细分析三次翻转 翻转 1: O(n) 翻转 2: O(k) 翻转 3: O(n-k) 总计: O(n) O(k) O(n-k) O(n) 空间 原地翻转使用常数额外空间 O(1)七、面试追问 FAQ问题回答要点Q: 为什么三次翻转能实现轮转整体翻转改变顺序前后分别翻转抵消了整体翻转带来的逆序最终得到正确顺序Q: k % n 的作用是什么防止 k 大于数组长度k10, n7 等价于 k3避免不必要的翻转Q: 能否只翻转一次不能一次翻转只能反转顺序无法实现轮转Q: 三次翻转的时间复杂度是多少O(n)三次翻转的总时间之和为 O(n)Q: 环状替换和三次翻转哪个更好三次翻转代码更简单面试中推荐环状替换需要处理 gcd较复杂Q: 如何向左轮转将 k 改为 n-k或者修改翻转顺序先翻前后两段再整体翻转Q: 能用队列模拟吗可以每次 pop_front 再 push_back但时间复杂度 O(n*k)会超时八、相关题目题目编号题目名称难度核心差异189轮转数组中等基础题向右轮转61旋转链表中等旋转链表非数组151反转字符串中的单词中等先整体翻转再分段翻转796旋转字符串简单判断是否为旋转串剑指 Offer 58左旋转字符串简单向左轮转九、总结要点内容核心思想三次翻转整体 - 前k - 后n-k关键操作k % n防止越界时间复杂度O(n)三次翻转空间复杂度O(1)原地操作代码行数仅 4 行简洁高效注意事项k 可能大于 n需要取模变形向左轮转将 k 改为 n-k或修改翻转顺序三次翻转法是轮转数组的最优解代码简洁面试中容易通过建议熟练掌握。