原位旋转指不借助额外数组、仅通过元素交换实现数组循环移位；正确方法是三次反转法（整体反转+前k反转+后n−k反转）或环状替换，避免使用临时容器导致O(n)空间复杂度。
什么是原位旋转？为什么不能用临时数组
原位旋转指不借助额外的 std::vector 或动态分配内存，仅靠交换元素完成数组循环移位。常见误区是用 std::rotate 却没注意它底层是否分配内存——其实标准库的 std::rotate 是原位的（C++11 起保证 O(1) 空间），但很多人自己手写时误用临时容器，导致空间复杂度变成 O(n)。
真正需要警惕的是「模拟旋转」场景：比如把长度为 n 的数组向右移动 k 位，等价于将后 k 个元素移到前面。此时若用 temp 数组暂存后 k 个，就违背了原位要求。
- 错误做法：
std::vector<int> temp(arr.end() - k, arr.end())</int>→ 额外 O(k) 空间 - 正确思路：三次反转法（reverse）或环状替换（cycle swapping）
- 反转法更易懂、不易出错；环状替换理论上更省 swap 次数，但需处理 gcd 和索引跳转
三次反转法：最稳妥的原位实现
核心观察：右移 k 位 = 先整体反转，再反转前 k 个，再反转后 n−k 个。例如 [1,2,3,4,5] 右移 2 位 → [4,5,1,2,3]，过程如下：
原始: [1,2,3,4,5] 整体反转: [5,4,3,2,1] 反转前2: [4,5,3,2,1] 反转后3: [4,5,1,2,3]
关键点：每次反转都用双指针 in-place 完成，无额外空间。
立即学习“C++免费学习笔记（深入）”；
- k 需先对 n 取模：
k = k % n，避免无效旋转 - 反转函数必须接受迭代器或下标范围，不能复制子数组
- 边界处理：当
k == 0或n == 0时直接返回，避免越界
示例（C++11+）：
void reverse(vector<int>& arr, int l, int r) {
while (l < r) swap(arr[l++], arr[r--]);
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) return;
k = k % n;
reverse(nums, 0, n-1);
reverse(nums, 0, k-1);
reverse(nums, k, n-1);
}环状替换法：swap 次数最少，但容易写错索引
适用于对性能极度敏感的场景（比如嵌入式或超大数组），理论 swap 次数恰好是 n 次，而三次反转法约 3n/2 次 swap。但它依赖环的分解：从位置 0 开始，每次跳 (i + k) % n，直到回到起点，构成一个环；重复直到所有元素被访问。
- 必须记录已访问位置，否则会死循环 —— 常见错误是漏掉
visited数组或用变量计数但未校验总数 - 实际中常用计数器
count替代布尔数组，避免额外 O(n) 空间：if (count == n) break; - 环长由
gcd(n, k)决定，总环数也是gcd(n, k)，但代码里无需显式计算 - 起始点选 0 最简单；若 k 和 n 不互质，必须多轮启动（如 k=2, n=4 时环为 0→2→0 和 1→3→1）
std::rotate 能否直接用？要注意什么
可以，且推荐在业务代码中优先使用 std::rotate —— 它是标准库保证原位、稳定、高效（通常用类似三次反转的策略实现）。但有两个易忽略细节：
- 参数顺序是
std::rotate(first, middle, last)，其中[first, middle)被移到末尾，即右移等价于middle = nums.begin() + n - k - 如果传错
middle（比如写成+k而非+n-k），结果是左移，且可能越界触发 undefined behavior - 对 raw array 需配合
std::begin/std::end，不能直接传指针算术（除非确保类型安全）
正确调用：
std::rotate(nums.begin(), nums.begin() + (n - k % n), nums.end());
环状替换的边界条件和 gcd 计算最容易被跳过，而三次反转法虽多几次 swap，但逻辑清晰、调试友好——多数情况下，选它更省时间。
