做网站的流程方法,做高端生活方式的网站,特产网站建设的目的,2023最建议买10款手机目录
插入操作#xff08;Inserting in an Array#xff09;
在纸上模拟你会怎么做#xff1f;
代码实现
复杂度分析
删除操作#xff08;Deleting from an Array#xff09;
在纸上模拟一下怎么做#xff1f;
代码实现
复杂度分析 插入操作#xff08;Inserti…目录
插入操作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是的插入后 length1插入到尾部就是 A[length] value 复杂度分析
时间复杂度分析
移动次数依赖于插入位置
插入位置 pos向后移动的元素个数最坏的移动数最前面pos 0n 个元素需要后移✅ 最坏情况 O(n)中间pos n/2n/2 个元素后移平均情况 O(n)最末尾pos n0 个元素移动✅ 最好情况 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]覆盖 6A[4] 10 → A[3]覆盖 8
[2][4][8][10][10]最后一个 10 是重复的可以忽略或者设置为0、垃圾值
代码实现
删除操作的本质 删除数组中某个位置的元素需要从后往前逐个移动元素来“填空”最后更新长度。 删除过程 从 pos1 开始把所有元素向前搬一格 覆盖掉被删除的元素 更新数组长度
void deleteAt(int A[], int length, int pos) {// 1. 从 pos1 开始向前搬一格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
你需要移动一半的元素从 pos1 到 n−1 移动次数 ≈ n/2
时间复杂度仍是 O(n)常数系数不影响阶
情况三删除最后一个元素pos n - 1
你不需要移动任何元素直接逻辑删除即可
移动次数 0
最好情况O(1)
平均时间复杂度 如果删除位置是随机的每个位置被删除的概率相同那平均要移动 结论平均移动次数是 n - 1/2 平均时间复杂度也是 O(n)
✅ 空间复杂度 你没有开辟任何新空间 所有操作都是在原数组上完成
空间复杂度O(1)常数
