数据结构：数组：反转数组（Reverse the Array）

目录

🎯问题描述

从第一性原理出发：怎么“反”？

代码实现

方法二：使用一个额外数组来存放反转结果

代码实现

🎯问题描述

给定一个数组：

A = [1, 2, 3, 4, 5]

我们要把它反过来，变成：

A = [5, 4, 3, 2, 1]

从第一性原理出发：怎么“反”？

你可以这样问自己：

什么叫“反转”数组？

• 第一个变成最后一个

• 第二个变成倒数第二个

• 第三个……中间就不用动了（对称）

直观分析 — 谁和谁换位置？

数组长度为 5（即 n = 5）

我们可以发现：

• A[0] 和 A[4] 交换

• A[1] 和 A[3] 交换

• A[2] 无需动

总结操作模式

用两个指针：i 从左边开始，j 从右边开始
不断交换 A[i] 和 A[j]，直到两者相遇或交错

代码实现

✅ Step 1：定义两个指针（i 和 j）

我们从左边设 i = 0，从右边设 j = n - 1：

int i = 0;
int j = n - 1;

✅ Step 2：添加循环结构

只要 i < j 就继续交换，表示两边没有交错：

while (i < j) {
    // 交换 A[i] 和 A[j]
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;

    // 移动指针
    i++;
    j--;
}

✅ Step 3：把这段代码插入主函数中

#include <iostream>
using namespace std;

int main() {
    int A[] = {1, 2, 3, 4, 5};
    int n = sizeof(A) / sizeof(A[0]);

    int i = 0;
    int j = n - 1;

    while (i < j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;

        i++;
        j--;
    }

    // 输出反转后的数组
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }

    return 0;
}

总结操作次数：

• 数组长度为 n

• 总共交换次数为 [ n / 2 ]

• 每次交换只花 O(1) 时间

时间复杂度分析

• 每次交换是 O(1)

• 总共交换 n/2 次

• 所以时间复杂度是：O(n​) 

空间复杂度分析

• 我们只用了两个变量 i 和 j

• 没有额外开辟数组

• 所以空间复杂度是：O(1​) 

🧩一句话总结：

用两个指针从两端向中间交换，就能原地反转一个数组，时间复杂度是 O(n)，空间复杂度是 O(1)。

方法二：使用一个额外数组来存放反转结果

你现在问自己：

如果我不想就地交换，而是重新开一个数组，能不能把反转后的结果存进去？

当然可以！这是一个空间换时间的经典思路。

🧠 基本策略：

给定原数组 A 长度为 n，我们：

1. 声明一个新数组 B[n]

2. 用一个循环，把 A 的元素从 末尾向前放入 B 的前面

3. 最后再把 B 中的值 复制回 A 中，完成反转

代码实现

✅ Step 1：定义数组并计算长度

我们还是用例子：

int A[] = {1, 2, 3, 4, 5};
int n = sizeof(A) / sizeof(A[0]);

✅ Step 2：声明新数组 B[n]

int B[n];

✅ Step 3：反转填入 B

我们用一个循环：

for (int i = 0; i < n; i++) {
    B[i] = A[n - 1 - i];
}

说明：

• 当 i = 0 → B[0] = A[4]

• 当 i = 1 → B[1] = A[3]

• …

• 正好完成反转

✅ Step 4：把 B 复制回 A

for (int i = 0; i < n; i++) {
    A[i] = B[i];
}

 完整代码

#include <iostream>
using namespace std;

int main() {
    int A[] = {1, 2, 3, 4, 5};
    int n = sizeof(A) / sizeof(A[0]);

    // 创建一个新数组
    int B[n];

    // 将 A 的元素反向复制到 B
    for (int i = 0; i < n; i++) {
        B[i] = A[n - 1 - i];
    }

    // 将 B 的结果复制回 A
    for (int i = 0; i < n; i++) {
        A[i] = B[i];
    }

    // 输出反转后的 A
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }

    return 0;
}

时间 & 空间复杂度分析：

🧩一句话总结：

使用一个同样大小的辅助数组，把 A 从尾到头复制到 B，再写回 A，
可以在不修改原数组逻辑的基础上完成反转，代价是额外空间。