C++怎样实现数组原位交换旋转（避免占用额外空间）

原位旋转指不借助额外数组、仅通过元素交换实现数组循环移位；正确方法是三次反转法（整体反转+前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&gt& 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，但逻辑清晰、调试友好——多数情况下，选它更省时间。