C++如何实现数组原位交换旋转(避免占用额外空间)-C++-PHP中文网

原位旋转指不借助额外数组、仅通过元素交换实现数组循环移位；正确方法是三次反转法（整体反转+前k反转+后n−k反转）或环状替换，避免使用临时容器导致O(n)空间复杂度。

c++如何实现数组原位交换旋转(避免占用额外空间)

什么是原位旋转？为什么不能用临时数组

原位旋转指不借助额外的 std::vector 或动态分配内存，仅靠交换元素完成数组循环移位。常见误区是用 std::rotate 却没注意它底层是否分配内存——其实标准库的 std::rotate 是原位的（C++11 起保证 O(1) 空间），但很多人自己手写时误用临时容器，导致空间复杂度变成 O(n)。

真正需要警惕的是「模拟旋转」场景：比如把长度为 n 的数组向右移动 k 位，等价于将后 k 个元素移到前面。此时若用 temp 数组暂存后 k 个，就违背了原位要求。

错误做法：std::vector temp(arr.end() - k, arr.end()) → 额外 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 完成，无额外空间。

k 需先对 n 取模：k = k % n，避免无效旋转
反转函数必须接受迭代器或下标范围，不能复制子数组
边界处理：当 k == 0 或 n == 0 时直接返回，避免越界

示例（C++11+）：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

void reverse(vector<int>& arr, int l, int r) {
    while (l <h3>环状替换法：swap 次数最少，但容易写错索引</h3>
<p>适用于对性能极度敏感的场景（比如嵌入式或超大数组），理论 swap 次数恰好是 n 次，而三次反转法约 3n/2 次 swap。但它依赖环的分解：从位置 0 开始，每次跳 <code>(i + k) % n</code>，直到回到起点，构成一个环；重复直到所有元素被访问。</p>
<ul>
<li>必须记录已访问位置，否则会死循环 —— 常见错误是漏掉 <code>visited</code> 数组或用变量计数但未校验总数</li>
<li>实际中常用计数器 <code>count</code> 替代布尔数组，避免额外 O(n) 空间：<code>if (count == n) break;</code>
</li>
<li>环长由 <code>gcd(n, k)</code> 决定，总环数也是 <code>gcd(n, k)</code>，但代码里无需显式计算</li>
<li>起始点选 0 最简单；若 k 和 n 不互质，必须多轮启动（如 k=2, n=4 时环为 0→2→0 和 1→3→1）</li>
</ul>
<h3>std::rotate 能否直接用？要注意什么</h3>
<p>可以，且推荐在业务代码中优先使用 <code>std::rotate</code> —— 它是标准库保证原位、稳定、高效（通常用类似三次反转的策略实现）。但有两个易忽略细节：</p>
<ul>
<li>参数顺序是 <code>std::rotate(first, middle, last)</code>，其中 <code>[first, middle)</code> 被移到末尾，即右移等价于 <code>middle = nums.begin() + n - k</code>
</li>
<li>如果传错 <code>middle</code>（比如写成 <code>+k</code> 而非 <code>+n-k</code>），结果是左移，且可能越界触发 undefined behavior</li>
<li>对 raw array 需配合 <code>std::begin</code>/<code>std::end</code>，不能直接传指针算术（除非确保类型安全）</li>
</ul>
<p>正确调用：</p>
<pre class="brush:php;toolbar:false;">std::rotate(nums.begin(), nums.begin() + (n - k % n), nums.end());

环状替换的边界条件和 gcd 计算最容易被跳过，而三次反转法虽多几次 swap，但逻辑清晰、调试友好——多数情况下，选它更省时间。