数据结构:数组:反转数组(Reverse the Array)

发布于:2025-07-10 ⋅ 阅读:(23) ⋅ 点赞:(0)

目录

🎯问题描述

从第一性原理出发:怎么“反”?

代码实现

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

代码实现


🎯问题描述

给定一个数组:

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] A[2](中间,无需动)
A[3] A[1]
A[4] A[0]

我们可以发现:

  • 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 = 0B[0] = A[4]

  • i = 1B[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;
}

时间 & 空间复杂度分析:

操作 次数 复杂度
复制到 B n 次 O(n)
复制回 A n 次 O(n)
总时间 2n O(n)
额外空间 使用了 B O(n)

🧩一句话总结:

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


网站公告

今日签到

点亮在社区的每一天
去签到