原位旋转是指在o(1)额外空间下通过元素交换实现数组循环移位，不能用临时数组；因其违反空间约束且不适用于嵌入式等场景，正确解法为三次翻转法或环状替换法，前者更稳定安全。
什么是原位旋转？为什么不能用临时数组
原位旋转指在不申请额外数组空间（O(1) 额外空间）的前提下，通过反复交换元素，把数组 arr 向右（或向左）循环移动 k 位。常见误区是直接用 std::vector 或 new 分配新数组——这违反“不占空间”要求，且在嵌入式、高频交易等场景会被拒绝。
真正可行的思路只有两种：三次反转法（推荐）或环状替换法（易错）。前者逻辑清晰、边界稳定；后者理论上更省 swap 次数，但下标计算极易越界或漏元素。
三次反转法：最稳的 O(n) 时间 + O(1) 空间解法
核心思想：右移 k 位 = 先整体反转，再反转前 k 个，再反转后 n-k 个。数学上等价，且每步只用双指针 in-place 交换，无索引偏移风险。
注意：k 必须先对长度取模，否则 k > n 时会出错：
void rotate(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) return;
k = k % n; // 关键！否则反转范围越界
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}</int>
-
k % n不可省略——k=7, n=3时等价于k=1，否则nums.begin()+k会越界 - 三次
reverse调用都是标准库函数，底层即双指针 swap，无额外内存分配 - 若用 raw array（如
int arr[10]），需手动写双指针 swap 循环，不能直接调std::reverse
环状替换法：swap 次数最少但极易写错
该方法把数组看作若干独立循环链，每个循环长度为 n / gcd(n, k)，总循环数为 gcd(n, k)。它只做恰好 n 次 swap，理论最优，但下标更新公式稍有不慎就陷入死循环或跳过元素。
关键陷阱：
- 起始位置必须遍历
0到gcd(n,k)-1，而非0到n-1 - 每次循环内，当前索引更新为
(i + k) % n，但必须用临时变量存原始值，否则覆盖 - 忘记重置
count或start导致部分元素未处理（尤其k和n不互质时）
示例片段（仅示意逻辑，实际需严格校验）：
int count = 0, start = 0; while (count <h3>边界与性能：不同场景怎么选</h3><p>三次反转法在所有情况下都安全，且现代 CPU 对连续内存访问友好，实际性能常优于环状替换（后者 cache miss 更多）。环状替换仅在极端内存受限且 <code>k</code> 已知为小整数时值得尝试。</p><p>真实踩坑点：</p>
- 输入为空或
n==1时，k % n会触发除零错误——务必先判空 - 使用
int存k但未检查是否为负——C++ 中负数取模结果依赖编译器，应先k = ((k % n) + n) % n - 误以为
std::rotate是原位——它确实是，但内部实现就是三次反转，直接用它最省心：std::rotate(nums.begin(), nums.begin() + (n - k % n), nums.end());
真正难的不是写对，而是想明白：为什么三次反转能等价于循环移位？动手画三个长度为 6 的数组，分别标出每步反转的区间，比看十遍公式管用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
