在之間的兩篇文章中，我們著重講了順序表及順序表的實現。今天這篇文章我們將簡單講解關于順

序表的三個算法題。這三個題也都屬于力扣上的經典例題。

1.例題1:移除元素

方法二 : 借助數組法

int removeElement(int* nums, int numsSize, int val) 
{// 動態分配一個與原數組大小相同的臨時數組，處理 numsSize 為 0 的情況避免非法int* tmp = (int*)malloc(numsSize * sizeof(int));   if(tmp == NULL){return 0;}int index = 0;  // 記錄新數組 tmp 的下標，用于存放不等于 val 的元素for(int i = 0;i<numsSize;i++){if(nums[i]!=val){tmp[index] = nums[i];index++;}}// 將臨時數組中有效元素（不等于 val 的元素）拷貝回原數組前 index 個位置for(int i = 0;i<index;i++){nums[i] = tmp[i];}free(tmp);  // 釋放臨時數組內存，避免內存泄漏return index;
}

思路：

- 首先動態分配一個和原數組 nums?大小相同的臨時數組?tmp，用于存儲不等于 val?的元

素。若內存分配失敗（?tmp == NULL??），直接返回 0。

- 遍歷原數組 ?nums??，當遇到元素不等于 ?val??時，將其存入臨時數組 tmp?中，同時

用?index??記錄 ?tmp??中有效元素的個數（即下標 ）。

- 遍歷結束后，把臨時數組 ?tmp??中存儲的有效元素（共 ?index??個 ）拷貝回原數組nums?的

前 index?個位置，最后釋放臨時數組 tmp?的內存，避免內存泄漏，返回 index??，即原數組中

不等于 val?的元素數量。

時間復雜度：

- 遍歷原數組 ?nums??是一個 O(n) 的操作（?n??為數組初始長度 ?numsSize??），將臨時數組元

素拷貝回原數組也是一個 O(k) 的操作（?k??為不等于 ?val??的元素數量，最大為 ?n??），總的

時間復雜度為 O(n) ，因為 O(n + k) 中 ?k??最大不超過 ?n??，可簡化為 O(n) 。

空間復雜度：

- 額外動態分配了一個大小為 ?numsSize??的臨時數組 ?tmp??，所以空間復雜度為 O(n)?。

方法三?:??雙指針法（推薦的高效原地算法 ）

int removeElement(int* nums, int numsSize, int val) 
{int dst = 0,src = 0; while(src < numsSize){// 當 src 指向元素不等于 val 時，將其賦值到 dst 位置，dst 后移if(nums[src] != val) {nums[dst] = nums[src];dst++;}src++; }return dst;
}

思路：

- 定義兩個指針（這里用變量 dst 和 src?模擬指針功能 ），src?用于遍歷原數組?nums??，逐個

檢查元素；?dst??用于標記新數組（即處理后不含 val?的數組部分 ）的最后一個位置。

- 遍歷過程中，當 ?nums[src]??不等于 ?val??時，說明該元素是需要保留的，將其賦值到

nums[dst]?的位置，然后 dst?自增 1，指向下一個要填充的位置；不管 nums[src]?是否等于

?val?，src?都要自增 1 ，繼續遍歷下一個元素。

- 當 ?src??遍歷完整個數組（?src >= numsSize??）時，?dst??的值就是原數組中不等于 ?val??的

元素數量，且原數組前 ?dst??個元素已經是處理后不含 ?val??的結果。

時間復雜度：

- 只需遍歷一次原數組 ?nums??，?src??從 0 走到 ?numsSize - 1??，循環執行 ?numsSize??次，

所以時間復雜度為 O(n) ，其中 ?n??是數組 ?nums??的初始長度 。

空間復雜度：

- 只使用了常數個額外變量（?dst?、?src??），沒有額外開辟大量數據存儲空間，空間復雜度

為 O(1) ，屬于高效的原地算法。

2.例題2:刪除有序數組中的重復項

方法 : 雙指針解法

int removeDuplicates(int* nums, int numsSize) {// dst 初始指向第 1 個唯一元素應在的位置（初始為 0）int dst = 0, src = dst + 1; // src 遍歷整個數組，找后續元素while (src < numsSize) { // 條件 1：當前 src 元素與 dst 元素不同（需保留 src 元素）// 條件 2：++dst != src（嘗試移動 dst 后，判斷是否與 src 位置重疊）if (nums[src] != nums[dst] && ++dst != src) { // 將 src 元素放到 dst 位置，保證前 dst+1 個元素唯一nums[dst] = nums[src]; }// src 繼續向后遍歷src++; }// dst 是最后一個唯一元素的下標，長度為下標 + 1return dst + 1; 
}

思路（以 ?nums = [1,1,2]??為例 ）:

1.?初始狀態：?dst = 0?（指向第一個 ?1??），?src = 1?（指向第二個 ?1??）。

2.?第一次循環：?nums[src] == nums[dst]?（都是 1?），足?nums[src]!=nums[dst]?，?src++?→

src = 2?。

3.?第二次循環：?nums[src] = 2??≠ ?nums[dst] = 1?，執行 ?++dst?（?dst = 1??），判斷 ?dst !=

src?（?1 != 2??→ 成立 ），執行 ?nums[1] = 2?，數組變為 ?[1,2,2]?；?src++??→ ?src = 3?（退出

循環 ）。

4.?返回結果：?dst + 1 = 2?，與題目要求一致。

復雜度分析:

時間復雜度:

- 核心邏輯：?src??從 ?1??遍歷到 ?numsSize - 1?，僅遍歷數組一次。

- 無論數組多長，循環次數為 ?numsSize - 1?（?src??移動次數 ），因此時間復雜度為

?O(n)（?n??為numsSize?，即數組長度 ）。

空間復雜度:

- 函數僅使用 ?dst?、?src??兩個額外變量，未動態分配內存（如 ?malloc??）。

- 額外空間占用與數組長度無關，始終為常數，因此空間復雜度為 ?O(1)?（原地算法 ）。

3.例題3:合并兩個有序數組

方法一 :?先合并再冒泡排序

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{// 1. 合并 nums2 到 nums1 中int k = 0;for (int i = m; i < m + n; i++) {nums1[i] = nums2[k];k++;}// 2. 冒泡排序實現升序排列int len = m + n;for (int i = 0; i < len - 1; i++) {for (int j = 0; j < len - i - 1; j++) {if (nums1[j] > nums1[j + 1]) {// 交換元素int temp = nums1[j];nums1[j] = nums1[j + 1];nums1[j + 1] = temp;}}}
}

思路:

- 合并階段：利用循環，把 ?nums2??中的元素依次放到 ?nums1??中原本后面閑置的位置（即

從下標 ?m??開始的位置 ），完成兩個數組合并為一個數組的操作。

- 排序階段：采用冒泡排序，對合并后的 ?nums1??數組（長度為 ?m + n??）進行升序排序，通

過相鄰元素比較和交換，讓整個數組有序。

復雜度分析：

- 時間復雜度：合并操作是 ?O(n)?（?n??是 ?nums2??的長度 ），冒泡排序的時間復雜度是

?O((m + n)2)??。總的時間復雜度由冒泡排序主導，為?O((m + n)2)??，因為 ?(m + n)2??增長速度

比 ?n??快得多。

- 空間復雜度：整個過程只用到了幾個臨時變量（如 ?k?、?i?、?j?、?temp??等 ），沒有額外開

辟大量數據存儲空間，空間復雜度是 ?O(1)??。

方法二 :?先合并再快速排序（借助 qsort? 排序法)

// 比較函數，用于 qsort，實現升序排序
int compare(const void *a, const void *b)
{return (*(int *)a - *(int *)b);
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{// 1. 合并 nums2 到 nums1 中int k = 0;for (int i = m; i < m + n; i++) {nums1[i] = nums2[k];k++;}// 2. 使用 qsort 對合并后的 nums1 進行升序排序qsort(nums1, m + n, sizeof(int), compare);
}

思路：

- 合并階段：和方法一一樣，通過循環將 ?nums2??的元素放到 ?nums1??后面的閑置位置，完

成合并。

- 排序階段：調用標準庫函數 ?qsort??對合并后的 ?nums1??數組進行升序排序。?qsort??內部一

般采用快速排序算法（優化版本，平均情況高效 ），根據自定義的 ?compare??比較函數（返

回 ?a - b??實現升序 ）來排序。

復雜度分析：

- 時間復雜度：合并操作時間復雜度是 ?O(n)??。?qsort??基于快速排序，平均時間復雜度是

?O((m + n)log(m + n))??，最壞情況（比如數組完全有序等極端情況，快速排序退化為冒泡排

序邏輯，但實際 ?qsort??有優化，一般不考慮 ）時間復雜度是 ?O((m + n)2)??，這里按平均情

況，總的時間復雜度由 ?qsort??主導，為 ?O((m + n)log(m + n))??。

- 空間復雜度：合并階段空間復雜度 ?O(1)??，?qsort??內部實現可能會用到遞歸棧或者額外的

輔助空間，不過空間復雜度平均情況是 ?O(log(m + n))?（遞歸棧深度 ），最壞情況是 ?O(m +

n)??，但整體相對于方法一在排序環節更高效。

方法三 :?雙指針（從后往前合并）

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int l1 = m - 1;  // nums1 中有效元素（即原本要合并的元素）的最后一個下標int l2 = n - 1;  // nums2 中元素的最后一個下標int l3 = m + n - 1;  // 合并后 nums1 數組的最后一個下標// 同時遍歷 nums1 和 nums2 的有效元素（從后往前）while (l1 >= 0 && l2 >= 0) {if (nums1[l1] > nums2[l2]) {// nums1 當前元素更大，放到合并后數組的當前最后位置nums1[l3--] = nums1[l1--];} else {// nums2 當前元素更大或相等，放到合并后數組的當前最后位置nums1[l3--] = nums2[l2--];}}// 如果 nums2 還有剩余元素（說明 nums1 有效元素已經處理完了），直接放到 nums1 前面位置while (l2 >= 0) {nums1[l3--] = nums2[l2--];}
}

思路：

- 利用三個指針，?l1??指向 ?nums1??中原有有效元素的末尾，?l2??指向 ?nums2??元素的末

尾，?l3??指向合并后 ?nums1??數組的末尾。

- 從后往前比較 ?nums1??和 ?nums2??中的元素，把較大的元素放到 ?nums1??中? l3??指向的位

置，然后對應的指針向前移動。

- 當 ?nums1??原有有效元素處理完（?l1 < 0??），如果 ?nums2??還有剩余元素（?l2 >= 0??），

直接把這些元素依次放到 ?nums1??中剩下的位置，因為 ?nums2??本身是有序的，這樣就能保

證合并后整體有序。

復雜度分析：

- 時間復雜度：整個過程中，?l1??從 ?m - 1??往前遍歷到 ?-1??，?l2??從 ?n - 1??往前遍歷到

?-1??，?l3??從 ?m + n - 1??往前遍歷到 ?-1??，總的操作次數是 ?m + n??次，所以時間復雜度是

?O(m + n)??。

- 空間復雜度：只用到了幾個指針變量（?l1?、?l2?、?l3??），沒有額外開辟大量數據存儲空

間，空間復雜度是 ?O(1)??。