【力扣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 - 1
• 0 <= k <= 10^5

解题思路总览

一、三次翻转法（最常用）

核心思想

通过三次反转操作，将数组向右轮转 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(vector<int>&nums,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 例如 n=7, k=10 k %= n = 3 等价于轮转 3 位 结果正确

三、逐行解析

k%=nums.size();

• 取模，防止 k 大于数组长度
• 例如 n=7, k=10，k %= 7 = 3，等价于轮转 3 位
• 当 k = 0 或 k = n 时，结果和原数组一样

ranges::reverse(nums);

• C++20 的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 -> 新位置 (0+k) % n = 3 原位置 1 -> 新位置 (1+k) % 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(vector<int>&nums,intk){k%=nums.size();intn=nums.size();intcount=0;// 已放置的元素个数for(intstart=0;count<n;start++){intcurr=start;intprev=nums[start];do{intnext=(curr+k)%n;inttemp=nums[next];nums[next]=prev;prev=temp;curr=next;count++;}while(curr!=start);count++;// 补偿最后一次多减的}}};

与三次翻转法对比

六、复杂度分析

详细分析：

三次翻转： 翻转 1: O(n) 翻转 2: O(k) 翻转 3: O(n-k) 总计: O(n) + O(k) + O(n-k) = O(n) 空间： 原地翻转，使用常数额外空间 O(1)

七、面试追问 FAQ

八、相关题目

九、总结

三次翻转法是轮转数组的最优解，代码简洁，面试中容易通过，建议熟练掌握。