目录
插入操作（Inserting in an Array）
在纸上模拟你会怎么做？
代码实现
复杂度分析
删除操作（Deleting from an Array）
在纸上模拟一下怎么做？
代码实现
复杂度分析
插入操作（Inserting in an Array）
我们要讲的是：在一个数组中插入一个新元素，在任意合法的位置上，保持其他元素的顺序不乱。
给定一个数组：
A = [2, 4, 6, 8, 10]
现在你希望：在第 索引 2（也就是元素 6 之前）插入一个数字 99。
A = [2, 4, 99, 6, 8, 10]
在纸上模拟你会怎么做？
如果你用笔把这些数字排在格子里，加入一个空格，你会发现：
✅ 第一步：把从第2个位置开始的元素都向后移动一格，为99腾出位置。
[2][4][ ][6][8][10]↑插入位
你需要从右往左这样搬：
10 → [5] → [6]8 → [4] → [5]6 → [3] → [4]
✅ 第二步：然后把 99 放到空出的位置上（索引 2）
[2][4][99][6][8][10]
代码实现
你在做的是 一个插入操作，其本质逻辑是：
📌 思路：
从最后一个元素开始，逐个后移，直到你腾出目标位置为止，然后放入新元素。
插入操作的本质：
-
从插入位置开始，所有后面的元素向后移动一格
-
把新元素插入目标位置
-
长度 + 1
假设我们要在数组 A 中，插入 value 到索引 pos：
void insert(int A[], int& length, int pos, int value) {// 1. 从最后一个元素开始，向后搬运for (int i = length - 1; i >= pos; i--) {A[i + 1] = A[i]; // 向后挪一格}// 2. 把新值放进去A[pos] = value;// 3. 长度+1length++;
}
注意事项与边界处理
| 细节 | 说明 |
|---|---|
| 插入位置是否合法？ | 必须满足 0 ≤ pos ≤ length |
| 数组是否已满？ | 如果是静态数组，你必须预留空间 |
| 是否需要手动调整 length？ | 是的，插入后 length+1 |
| 插入到尾部？ | 就是 A[length] = value |
复杂度分析
时间复杂度分析
移动次数依赖于插入位置
插入位置 pos | 向后移动的元素个数 | 最坏的移动数 |
|---|---|---|
最前面（pos = 0） | n 个元素需要后移 | ✅ 最坏情况 O(n) |
中间（pos = n/2） | n/2 个元素后移 | 平均情况 O(n) |
最末尾（pos = n） | 0 个元素移动 | ✅ 最好情况 O(1) |
| 情况 | 移动次数 | 复杂度 |
|---|---|---|
| 最好情况（末尾插入） | 0 次移动 | O(1) |
| 最坏情况（头部插入） | n 次移动 | O(n) |
| 平均情况 | ≈ n/2 次移动 | O(n) |
✅ 因此，插入操作的总体时间复杂度为：O(n)
空间复杂度分析
-
如果你在原数组中操作（已有多余空间），空间复杂度是 O(1)（只需要一个临时变量）
-
如果你在 动态扩容数组 中插入（如
std::vector），插入时如果超容量，可能要分配新内存，空间复杂度变为 O(n)（拷贝新数组）
删除操作（Deleting from an Array）
在一个数组中删除某个位置上的元素，并保持其他元素的顺序不变。
A = [2, 4, 6, 8, 10]
你希望从中删除索引为 2 的元素 6，目标是：
A = [2, 4, 8, 10]
在纸上模拟一下怎么做？
你可以把数组想象成一排格子，每个格子装着一个数：
[2][4][6][8][10]↑ 要删掉的元素
你不能真正“删掉”一个格子 —— 因为数组的长度是固定的
你只能“覆盖”它。
你可以从删除位置的下一个元素开始，把它们往前搬一格，覆盖前面的内容：
| 从后往前搬 | 目标 |
|---|---|
| A[3] = 8 → A[2] | 覆盖 6 |
| A[4] = 10 → A[3] | 覆盖 8 |
[2][4][8][10][10]
（最后一个 10 是重复的，可以忽略，或者设置为0、垃圾值）
代码实现
删除操作的本质：
删除数组中某个位置的元素，需要从后往前逐个移动元素来“填空”，最后更新长度。
删除过程：
-
从
pos+1开始，把所有元素向前搬一格 -
覆盖掉被删除的元素
-
更新数组长度
void deleteAt(int A[], int& length, int pos) {// 1. 从 pos+1 开始，向前搬一格for (int i = pos + 1; i < length; i++) {A[i - 1] = A[i];}// 2. 长度减 1length--;
}
边界与注意事项
| 检查项 | 说明 |
|---|---|
| 删除位置是否有效？ | 0 ≤ pos < length |
| 是否需要更新数组长度？ | 是的，必须减 1 |
| 是否要清空最后一个位置？ | 通常不用，逻辑上长度变短即可 |
复杂度分析
✅ 时间复杂度
要移动多少个元素？需要花多少时间？
情况一：删除第一个元素（pos = 0）
你需要移动全部 n−1 个元素（A[1] → A[0], A[2] → A[1], ..., A[n−1] → A[n−2]）
所以：移动次数 = n - 1 → 最坏情况
时间复杂度：O(n)
情况二：删除中间位置（pos = n/2）
你需要移动一半的元素（从 pos+1 到 n−1）
移动次数 ≈ n/2
时间复杂度仍是 O(n)（常数系数不影响阶）
情况三：删除最后一个元素（pos = n - 1）
你不需要移动任何元素，直接逻辑删除即可
移动次数 = 0
最好情况：O(1)
平均时间复杂度
如果删除位置是随机的，每个位置被删除的概率相同，那平均要移动：
结论：平均移动次数是 （n - 1）/2
🕒 平均时间复杂度也是 O(n)
✅ 空间复杂度
-
你没有开辟任何新空间
-
所有操作都是在原数组上完成
空间复杂度：O(1)（常数）
)
