目錄
插入操作（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)（常數）
)
