数据结构 顺序表(3)---顺序表的应用

在之间的两篇文章中，我们着重讲了顺序表及顺序表的实现。今天这篇文章我们将简单讲解关于顺

序表的三个算法题。这三个题也都属于力扣上的经典例题。

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)²)  。总的时间复杂度由冒泡排序主导，为 O((m + n)²)  ，因为  (m + n)²  增长速度

比  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)²)  ，这里按平均情

况，总的时间复杂度由  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)  。