C++数组移动：n个整数前移m位，后m个数前置，如何高效实现？

Question

**如何高效实现C++数组中n个整数前移m位并将后m个数前置？** 在C++中，若要将一个包含n个整数的数组前移m位，并将最后m个元素移动到数组前面，如何以时间和空间高效的方式实现？例如，数组`[1, 2, 3, 4, 5]`，当`m=2`时，结果应为`[4, 5, 1, 2, 3]`。常见的方法包括使用额外数组存储后m个元素再重新排列，但这种方式增加了空间复杂度。更优的解法是通过原地旋转数组：先反转整个数组，再分别反转前m个和后n-m个元素。这种方法仅需常数级额外空间，时间复杂度为O(n)。如何用C++标准库函数（如`std::reverse`）优雅实现这一逻辑，同时保证代码简洁高效？

Answer 1

1. 问题分析与背景

在C++中，数组操作是一个常见的需求。对于将一个包含n个整数的数组前移m位并将最后m个元素移动到数组前面的问题，我们需要设计一种高效的方法来实现这一目标。直接使用额外数组存储后m个元素再重新排列是一种简单的方式，但会增加空间复杂度。

更优的解法是通过原地旋转数组：先反转整个数组，再分别反转前m个和后n-m个元素。这种方法仅需常数级额外空间，时间复杂度为O(n)。

常见方法对比

方法	时间复杂度	空间复杂度
使用额外数组	O(n)	O(n)
原地旋转数组	O(n)	O(1)

因此，我们选择原地旋转数组作为解决方案。

2. 解决方案设计

为了实现高效的数组旋转，我们可以利用C++标准库中的`std::reverse`函数。以下是具体的步骤：

1. 反转整个数组。
2. 反转数组的前m个元素。
3. 反转数组的后n-m个元素。

这种三步反转法可以确保数组在原地完成旋转，而无需额外的空间开销。

3. 实现代码

以下是基于C++标准库函数`std::reverse`的实现代码：

#include <iostream>
#include <vector>
#include <algorithm>

void rotateArray(std::vector<int>& nums, int m) {
    int n = nums.size();
    m = m % n; // 确保m在有效范围内
    if (m == 0) return;

    // 第一步：反转整个数组
    std::reverse(nums.begin(), nums.end());
    
    // 第二步：反转前m个元素
    std::reverse(nums.begin(), nums.begin() + m);
    
    // 第三步：反转后n-m个元素
    std::reverse(nums.begin() + m, nums.end());
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    int m = 2;
    rotateArray(nums, m);

    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

4. 流程图解析

以下是一个流程图，展示了上述算法的执行过程：

graph TD
    A[输入数组] --"反转整个数组"--> B{反转后的数组}
    B --"反转前m个元素"--> C{部分反转后的数组}
    C --"反转后n-m个元素"--> D[最终结果]

例如，对于数组`[1, 2, 3, 4, 5]`和`m=2`：

• 第一步：反转整个数组，得到`[5, 4, 3, 2, 1]`。
• 第二步：反转前m个元素，得到`[4, 5, 3, 2, 1]`。
• 第三步：反转后n-m个元素，得到`[4, 5, 1, 2, 3]`。

5. 进一步优化与扩展

虽然上述方法已经非常高效，但我们还可以考虑一些特殊情况：

• 当`m`大于数组长度时，可以通过取模运算简化问题：`m = m % n`。
• 当`m`为0或等于数组长度时，数组无需任何变化。

此外，该算法可以轻松扩展到其他数据结构（如链表）上，只需调整反转逻辑即可。