【Hot 100 刷题计划】 LeetCode 189. 轮转数组 | C++ 三次反转经典魔法 (O(1) 空间)

LeetCode 189. 轮转数组

📌 题目描述

题目级别：中等

给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。

进阶要求：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为O(1)的原地算法解决这个问题吗？

• 示例 1:
  输入:nums = [1,2,3,4,5,6,7], k = 3
  输出:[5,6,7,1,2,3,4]

💡 破题思路：三次反转 (数组魔术)

最容易想到的办法是开辟一个新数组，把后面的元素搬到前面，前面的搬到后面。但这会消耗 O(N) 的额外空间。
要想实现 O(1) 空间复杂度的“原地”轮转，最经典的解法就是**“三次反转法”**。

这就像是一个精妙的数学魔术。以nums = [1,2,3,4,5,6,7],k = 3为例，我们需要把最后 3 个元素搬到最前面。
按照本解法的独家顺序：

1. 反转前半段：把前n-k个元素反转。[1,2,3,4]变成了[4,3,2,1]。
   此时数组：[4,3,2,1, 5,6,7]
2. 反转后半段：把最后k个元素反转。[5,6,7]变成了[7,6,5]。
   此时数组：[4,3,2,1, 7,6,5]
3. 整体反转：把整个数组头尾对调！前面的去了后面，后面的来了前面，而且之前内部被打乱的顺序，在这一次整体反转中负负得正，完美还原！
   最终数组：[5,6,7, 1,2,3,4]

⚠️ 极客避坑点：
如果k的值比数组长度n还要大，比如数组长度为 7，让你轮转 10 次，其实就等价于轮转了10 % 7 = 3次。所以第一步必须进行取模运算k = k % n。

💻 C++ 代码实现

classSolution{public:voidrotate(vector<int>&nums,intk){intn=nums.size();// 核心细节：剥除多余的整圈轮转k=k%n;// 第一步：反转前半部分 (前 n-k 个元素)reverse(nums.begin(),nums.end()-k);// 第二步：反转后半部分 (后 k 个元素)reverse(nums.end()-k,nums.end());// 第三步：整体反转，首尾对调完成最终轮转reverse(nums.begin(),nums.end());}};