基于 Labuladong 的数组基础内容改编 https://labuladong.online/algo/data-structure-basic/array-basic/

你好！我是你的OI竞赛教练。今天我们回归本源，来讲讲所有数据结构的基石——数组 (Array)。

你可能觉得：“数组有什么好讲的？不就是 int a[100] 吗？” 但在 OI 竞赛和高阶算法面试中，理解数组的底层内存机制和扩容原理，是区分“会写代码”和“懂计算机原理”的关键。

---

OI 专题：数组原理与动态数组 (std::vector)

1. 数组的本质：连续存储 (Contiguous Memory)

在计算机内存中，数组不仅仅是一排数字，它有一个最严格的定义： 在连续的内存空间中，存储一组相同类型的元素。

为什么数组下标从 0 开始？

这是一个经典的偏移量（Offset）设计。 假设数组内存起始地址是 BaseAddress，每个元素占用 K 个字节。 想要访问第 i 个元素（下标 i）：

$$\text{Address}(i) = \text{BaseAddress} + i \times K $$

• 如果下标从 0 开始，i 就是偏移量，直接计算。
• 如果下标从 1 开始，公式变成 (i-1) * K，CPU 每次都要多做一次减法指令。为了极致的效率，C/C++ 选择了从 0 开始。

---

2. 核心特性：随机访问 (Random Access)

由于内存是连续的，且我们知道计算公式，所以： 数组访问任何一个位置的元素，时间复杂度都是 $O(1)$。

这被称为随机访问能力。这是数组最强大的武器，也是哈希表、堆等高级数据结构的基础。

---

3. 数组的代价：低效的插入与删除

既然“查”很快，那“改”呢？ 如果你想在数组中间插入一个元素，或者删除一个元素，为了保持“连续性”，必须移动后面的所有元素。

• 插入：把插入点之后的所有元素向后挪一位。
• 删除：把删除点之后的所有元素向前挪一位。
• 时间复杂度：平均情况 $O(N)$。

OI 警示：

在 $N=10^5$ 的题目中，如果你在循环里频繁进行数组中间的插入/删除操作，程序一定会 TLE (超时)。

---

4. 进阶武器：动态数组 (std::vector)

在 OI 竞赛中，我们经常不知道数据确切有多少个，开静态数组 int a[100005] 虽然常用，但 std::vector 更加灵活且安全。

4.1 动态扩容原理 (关键知识点)

Labuladong 重点提到了这点：计算机没有真正的“动态”内存。 std::vector 让你感觉它是无限延长的，其实底层是在演戏：

1. 初始化：申请一段固定大小的空间（例如 Capacity = 10）。
2. 填满时：当你 push_back 第 11 个元素时，发现空间不够了。
3. 扩容 (Reallocation)：
   • 申请一块更大的新内存区域（通常是原来的 1.5 倍或 2 倍）。
   • 搬家：将老数据全部拷贝到新内存中。
   • 销毁：释放旧内存空间。
   • 插入：放入新元素。

4.2 复杂度分析

• 普通 push_back：$O(1)$。
• 触发扩容时的 push_back：$O(N)$（因为要拷贝数据）。
• 均摊复杂度 (Amortized Complexity)：虽然偶尔有 $O(N)$，但平均下来，vector 的尾部插入依然被视为 $O(1)$。

---

5. 二维数组的内存布局

在 C++ 中，二维数组 int a[M][N] 本质上是一维数组的折叠。 它是“行优先” (Row-Major) 存储的。

这意味着：a[0][N-1] 的下一个地址紧接着 a[1][0]。 了解这一点对于空间局部性（Cache Locality）优化很有用：遍历二维数组时，先循环行、再循环列，速度最快。

---

6. OI 风格代码演示 (C++14)

这段代码展示了 vector 的基本操作、扩容机制观测以及二维数组的遍历。

/**
 * 知识点：数组基础与 vector 原理
 * 风格：OI 竞赛标准 C++14
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 1. IO 优化 (竞赛标配)
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // ------------------------------------------
    // Part 1: vector 的动态扩容演示
    // ------------------------------------------
    vector<int> v;
    // 预分配空间可以避免频繁扩容带来的性能损耗
    // v.reserve(100); // 竞赛技巧：如果我们大概知道 N 是多少，提前 reserve 
    
    cout << "--- Vector Growth ---" << endl;
    cout << "Size\tCapacity" << endl;
    
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
        // size: 实际元素个数
        // capacity: 当前分配的内存能容纳的个数
        cout << v.size() << "\t" << v.capacity() << endl;
    }
    // 观察输出，你会发现 capacity 是呈倍数增长的 (如 1, 2, 4, 8, 16...)

    // ------------------------------------------
    // Part 2: 随机访问与修改
    // ------------------------------------------
    if (!v.empty()) {
        v[5] = 999; // O(1) 修改
        cout << "\nAccess v[5]: " << v[5] << endl;
    }

    // ------------------------------------------
    // Part 3: 插入与删除 (慎用)
    // ------------------------------------------
    // 在头部插入，所有元素后移，O(N)
    v.insert(v.begin(), -1); 
    
    // 删除头部元素，所有元素前移，O(N)
    v.erase(v.begin());

    // ------------------------------------------
    // Part 4: 二维数组的高效遍历
    // ------------------------------------------
    int n = 3, m = 4;
    // 动态申请二维数组 vector<vector<int>>
    vector<vector<int>> matrix(n, vector<int>(m));

    int cnt = 0;
    // 推荐写法：行优先遍历 (Row-Major)
    // 这样顺应内存布局，Cache 命中率高
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            matrix[i][j] = ++cnt;
        }
    }

    return 0;
}

---

7. 课后总结 (Coach's Summary)

同学们，关于数组，请记住以下 3 个核心结论，做题时非常有用：

1. 下标是偏移量：所以从 0 开始最自然，访问速度是 $O(1)$。
2. Vector 不是魔法：它通过“倍增扩容”策略实现了伪动态。为了极致性能，如果你知道大概的数据量，请使用 v.reserve(N)。
3. 搬家很累：尽量避免在 vector 的头部或中间进行 insert 和 erase，那会导致 $O(N)$ 的复杂度。如果需要频繁在两头操作，请使用 std::deque；如果需要在中间频繁操作，请考虑链表。

下节课，我们将利用数组的 $O(1)$ 特性，结合双指针技巧，解决更复杂的算法题！

---

课后练习题：

教练收到了！

为了巩固刚才讲的 “二维数组内存布局” 和 “下标映射” 这两个核心概念，我为你设计了一道经典的 矩阵重塑 (Matrix Reshape) 题目。

这道题虽然是模拟题，但它直击数组的本质：无论二维数组怎么变，它在内存里都是一条线。

---

课后习题：矩阵的变形记

【题目描述】

小明正在做一个图像处理程序。计算机中的图像通常以 二维矩阵 的形式存储。 有时候，为了适配不同的屏幕，我们需要改变图像的尺寸，但不能改变图像中像素点的总数量和相对顺序。

现在给定一个 $R$ 行 $C$ 列的二维矩阵 $A$。 请你尝试将其“重塑”为一个新的 $r$ 行 $c$ 列的矩阵 $B$。

重塑规则：

1. 线性连续：你可以想象先把矩阵 $A$ 按照“行优先”的顺序展平成一个一维数组，然后再将这个一维数组按照“行优先”的顺序填充到新的 $r \times c$ 矩阵中。
2. 合法性检查：如果原矩阵 $A$ 的元素总数 ($R \times C$) 与新矩阵的要求 ($r \times c$) 不相等，说明无法进行重塑，此时请原样输出原矩阵 $A$。

【输入格式】

第一行包含两个整数 $R$ 和 $C$，表示原矩阵的行数和列数。 接下来 $R$ 行，每行包含 $C$ 个整数，表示原矩阵的元素。 最后一行包含两个整数 $r$ 和 $c$，表示目标矩阵的行数和列数。

【输出格式】

输出重塑后的矩阵。 如果无法重塑，输出原矩阵。 每行元素之间用空格分隔。

【样例 1】

输入

2 2
1 2
3 4
1 4

输出

1 2 3 4

解释： 原矩阵是 $2 \times 2$： [[1, 2], [3, 4]] 展平后是 [1, 2, 3, 4]。 重塑为 $1 \times 4$ 的矩阵，即 [[1, 2, 3, 4]]。

【样例 2】

输入

2 2
1 2
3 4
2 4

输出

1 2
3 4

解释： 原矩阵有 4 个元素，目标矩阵需要 $2 \times 4 = 8$ 个元素。数量不匹配，无法重塑，输出原矩阵。

【数据范围】

• $1 \le R, C \le 100$
• $1 \le r, c \le 100$
• $1 \le r \times c \le 10000$
• 矩阵元素为整数，且在 int 范围内。

---

【解题思路分析】

这道题的核心在于 “下标映射”。

1. 合法性判断： 首先检查 $R \times C$ 是否等于 $r \times c$。如果不等，直接输出原图。

2. 降维打击（逻辑层面）： 想象原矩阵 $A[i][j]$ 在内存中是连续排列的。 第 $i$ 行、第 $j$ 列的元素，它是整个扁平序列中的第 $k$ 个元素（$k$ 从 0 开始）。 映射公式：

   $$k = i \times C + j$$

3. 升维重组： 现在我们要把第 $k$ 个元素放入新矩阵 $B$ 的第 $x$ 行、第 $y$ 列。 根据新矩阵的列数 $c$，我们可以反推坐标：

   $$x = k / c$$ $$y = k \% c$$

总结：我们不需要真的创建一个一维数组来暂存数据（那样浪费空间）。我们可以直接用公式，把 $A[i][j]$ 填入 $B[k/c][k\%c]$，或者更简单地，直接遍历 $A$，顺手填入 $B$。

---

【参考代码 (C++14 OI Style)】

见题解

【教练点评】

这段代码展示了两种思维：

1. 物理视角：利用 new_row 和 new_col 手动维护新矩阵的写入位置。这是最直观的“模拟法”。
2. 数学视角（进阶）： 你也可以不维护 new_row/col，而是直接用一个循环 k 从 0 到 total-1（总数-1）： res[k / c][k % c] = mat[k / C][k % C]; 这行代码虽然短，但包含了对数组行优先存储深刻的理解。建议你在草稿纸上推导一下这个公式！