企业官网建设流程全解析

第二章-线性表 大题No.3 顺序表中删除所有值为x的元素

我最近在准备算法笔试的时候，重新把数据结构第二章线性表刷了一遍。刷到"顺序表中删除所有值为x的元素"这道大题时，我发现自己前前后后写了三种完全不同的写法，运行效率差了整整一个数量级。这道题看起来人畜无害，好像就是"遍历一遍，遇到x就删"，但真要在纸上写清楚、写对、写得让别人挑不出毛病，还真不是件容易事。它背后的考点其实很多：顺序表的内存连续性、删除操作的本质、原地操作的意识，还有边界条件设计。这篇文章我打算把这道题掰开揉碎讲清楚，从最直观的写法到最优解，从C语言实现到面试变体，给正在刷题或者准备考试的同学一个完整参考。

1. 为什么拿"删除x"来考顺序表：考点远比删元素本身深

先回到最基本的问题：顺序表到底是什么。所谓顺序表，就是用一段连续的内存来存放线性表的元素，在C语言里最常见的形式就是数组加一个长度变量。因为内存连续，我们可以在O(1)时间内通过下标访问任意元素，这是它的优势；但代价是，一旦涉及插入或删除，就必须批量搬移元素来维持"连续"这个前提。

这道题要删除所有值为x的元素，表面上是考察"你会不会写一个循环"，实际上考察的是你对"删除"这个概念的理解深度。在链表里删一个节点，只需要改几个指针；但在顺序表里删一个元素，意味着从删除位置开始，后面的所有元素都要往前挪一格，然后表的长度减一。所以顺序表的删除操作本身的时间复杂度是O(n)，n是表长。

更隐蔽的考点是：题目说的是"所有"值为x的元素。如果表里有多个x，而且它们还相邻，那么在删除过程中"跳过已经被删除的位置"就非常容易出错。我让A同学试了一下这道题，他第一版代码写的是：

int i = 0; while (i < L.length) { if (L.data[i] == x) { // 把后面的元素全部前移一位 for (int j = i; j < L.length - 1; j++) { L.data[j] = L.data[j + 1]; } L.length--; } else { i++; } }

这个写法能通过功能测试，但问题很大。如果数组中每个元素都是x，那么每删除一个元素就要搬移后面n-1个元素，整体复杂度是O(n²)。长度为10000的全x数组，就会产生5000万次赋值操作。很多教材把它称为"基本操作次数的平方增长"，但我更愿意用一个直白的说法：你把99个人排成一排，然后要求"凡是穿红衣服的都出列"，每出列一个人后面所有人都要往前挪一步，那队伍越长，挪的次数就越离谱。

这道题的深层考点其实有两点。第一，你是否意识到顺序表的存储特性决定了"任何位置删除"都是O(n)操作，"删除多个元素"如果每次都从被删位置搬移，就会累积出平方复杂度。第二，你是否能利用"遍历一次、原地覆盖"的思路，把O(n²)优化到O(n)。如果一个人上来就写双指针解法，说明他对这类问题已经有很强的"留出位置给后续元素"的直觉。

2. 三种删除思路：从O(n²)到O(n)的演进

这一节我用三种思路把这道题彻底讲透。其实重点不是"背下最优代码"，而是理解为什么后两种写法是等价的，以及它们各自适合在什么场景用。

2.1 逐个前移法：最直觉但最慢的写法

逐个前移法就是刚才那段代码，遍历时遇到x就执行一次"整体前移"。

它在思路上完全正确：删除一个元素后，数组仍然保持连续，剩余元素相对顺序不变。但性能上确实不理想，最坏情况下每个x后面的元素都要挪一遍。假设表长为n，里面有m个x，逐个前移法的总移动次数大约是m×n级别，因为每一次删除都涉及后面最多n-i个元素的前移。

这个方法的隐蔽风险还在于：删除完当前x之后，原本在它后面的元素会补到当前下标上，所以当前位置还要再检查一次。代码里用else分支处理i++，就是防止跳过连续x。有些同学写成"遇到x就前移，不管三七二十一i++"，那连续两个x就会漏删第二个，这是最常见的低错。

2.2 双指针覆盖法：把"删除"变成"保留"

真正高效的解法是把"删除哪些元素"反过来看，变成"保留哪些元素"。题目要求删除所有x，等价于"保留所有不等于x的元素，并且保持它们原有的相对顺序"。

既然是保留，就可以用两个下标：一个指针i负责遍历原数组，相当于"巡检工"；另一个指针k负责指向当前可写入的位置，相当于"留位员"。每当i发现当前元素不等于x，就把它复制到k指向的位置，然后k加一。遍历结束后，k的值就是新表的长度，直接把顺序表的length字段改成k即可。

int k = 0; for (int i = 0; i < L.length; i++) { if (L.data[i] != x) { L.data[k++] = L.data[i]; } } L.length = k;

这段代码总共只有五行，但它解决了所有问题。第一，它不会漏掉连续x，因为i永远只前进，不回头。第二，它不要求额外开辟数组，空间复杂度O(1)。第三，时间复杂度是O(n)，每个元素最多被移动一次。我用一个具体例子走一遍，表是[3, 7, 3, 3, 9, 3, 1, 3, 3, 5]，x=3：

遍历结束后k=4，所以新表长度就是4，最终得到[7, 9, 1, 5]。回头看这个写法，它最妙的地方在于：我们压根没有"删除"任何一个元素，而是有选择地把该留的往前移动，剩下的旧数据虽然还残留在数组后面，但已经不被length标记为有效了。就像整理书架时，不是把不要的书一本本抽出来，而是直接把要留的书一本本地往前面码，码完才知道书架有效长度是多少。

2.3 计数偏移法：另一双看透本质的眼睛

双指针法还有一种等价写法，在考研答题里也很常见：先统计已经遇到过多少个x，然后让每个非x元素前移"x的个数"位。

int cnt = 0; for (int i = 0; i < L.length; i++) { if (L.data[i] == x) { cnt++; } else { L.data[i - cnt] = L.data[i]; } } L.length -= cnt;

跟踪一下：当i遍历到第i个元素时，cnt恰好是"在0到i-1区间内已经遇到的x个数"，第i个非x元素要往左挪cnt位。为什么这个距离是固定的？因为前面的所有x都会被丢弃，每个x就空出一个位置，非x保留元素就需要整体前移这些空位的数量。

它和双指针法本质上是同一套逻辑：双指针的k等价于i-cnt。你仔细观察，双指针法里k = i - cnt 这个关系始终成立，因为每遇到一个x，k就比i少落后一位。两种写法，一个是直接用k记录目标位置，一个是通过计数间接计算出目标位置。考试时写哪一种都行，但个人建议先理解双指针法，因为它的状态更直观：k就是"下一个存活元素该放的位置"。

3. 完整实现与那些必须处理的边界条件

理论讲完，得落到能跑的代码上。我先给出一份基于结构体定义顺序表的C语言完整实现，然后重点说边界问题。

3.1 一版可以直接跑的C语言实现

顺序表的定义通常长这样：

#include <stdio.h> #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; int removeAllX(SeqList *L, int x) { if (L == NULL) { return -1; } int k = 0; for (int i = 0; i < L->length; i++) { if (L->data[i] != x) { L->data[k++] = L->data[i]; } } L->length = k; return k; }

这里我把函数设计成返回新表长度，而不是返回void，原因后面会专门讲。调用方拿到的返回值，既可用于验证删除是否真的发生，也可用于打印有效部分。

再给一个C++版本，因为很多人做题习惯用vector：

#include <vector> #include <algorithm> size_t removeAllX(std::vector<int>& v, int x) { size_t k = 0; for (size_t i = 0; i < v.size(); ++i) { if (v[i] != x) { v[k++] = v[i]; } } v.resize(k); return k; }

注意这里的坑：如果用STL的erase，有些人会顺手写一个O(n²)的循环，比如在循环条件里调用erase，导致迭代器失效或者反复搬移。更规范的STL写法是erase-remove惯用法：

v.erase(std::remove(v.begin(), v.end(), x), v.end());

std::remove本身就是一种分区算法，它的内部实现和双指针法完全一致。能直接看懂std::remove在干什么，才说明你真的理解了这道题。

3.2 十个容易被忽视的边界场景

做题时大部分人只测一个普通用例就收工，这是最要命的。我列一份比较完整的测试场景表，你写完代码后照着跑一遍，基本上就能杜绝低错。

我特别想强调"表里全是x"这个场景，它最能考验算法复杂度意识。本地上机时你可以加一个计时器，把表长加到十万，全填x，对比逐个前移法和双指针法的运行时间。前者能跑到几百毫秒甚至一秒以上，后者几乎是瞬间完成。这种直观的体感，比背一百遍"复杂度是O(n²)"都深刻。

3.3 为什么函数返回值比只改内部字段更可靠

我见过很多同学的函数写成这样：

void removeAllX(SeqList *L, int x) { // 删除过程... }

函数内部确实修改了L->length和L->data，从结果上说也能用。但有一个实际工程里的麻烦：调用方怎么知道表里到底有没有x？删了多少个？如果函数连删除数量都不返回，调用方就得自己遍历一遍去对比，这就多了一轮O(n)操作。

返回删除后长度或者返回删除的元素个数，信息量就大多了。比如我上面返回k（新长度），调用方可以自己算删除个数：原length - 新length。这个设计遵循一个很朴素的原则：一个函数应该尽量把它的操作结果明确告诉调用者，而不是让调用者猜。考试时有些阅卷标准也偏好返回删除后的表长，因为它直接体现你考虑了"表长变化"。

4. 面试和考试中这道题的常见变体

这道题几乎不会以原样单独出现，更多是作为基础模型被包装成各种变体。下面挑三个最常见的变体，每个我都说一下思路。

4.1 变体一：不要求保留相对顺序时如何更快

如果题目改成"删除所有值为x的元素，但不要求剩余元素保持原有相对顺序"，那性能还能进一步优化。思路是双指针从两端往中间夹逼：一个指针指向左边待处理元素，另一个指针指向右边有效元素。左边遇到x时，直接把右边指针所指的元素搬过来填补，然后右边指针左移；左边指针只有在搬来的元素不等于x时才右移。

int left = 0; int right = L.length - 1; while (left <= right) { if (L.data[left] == x) { L.data[left] = L.data[right]; right--; } else { left++; } } L.length = left;

这个做法的好处是：每个x被填充时用的是另一端"还没处理完的有效元素"，整体移动次数比双指针覆盖法更少，但代价是元素的相对顺序会被打乱。很多面试官喜欢用这个变体来考察"你是否意识到约束放松后可以换更激进的策略"。

4.2 变体二：删除有序顺序表中所有重复元素

如果是删除重复元素，而且前提是顺序表有序，那道题就变成了"去重"。这里不能用"删除所有值为x"的写法直接套，因为重复值有很多个，你要保留其中一个。最直接的做法还是双指针：一个指针i遍历，一个指针k记录去重后的写入位置；但判断条件不再是"不等于某个x"，而是"当前元素不同于前面一个保留元素"。

if (L.length == 0) return 0; int k = 1; for (int i = 1; i < L.length; i++) { if (L.data[i] != L.data[k - 1]) { L.data[k++] = L.data[i]; } } L.length = k;

这个变体在思路上多了一个"跟保留区最后一位比较"的动作。它告诉我们：双指针法不是某种固定写死的套路，而是一种把数组分区、原地整理的思想，判断条件完全可以根据题目要求调整。

4.3 变体三：从顺序表迁移到链表

如果题目改成链表形式，比如"删除单链表中所有值为x的节点"，那算法思路就要切换成"用一个指针遍历，另一个指针记录前驱节点，找到x就跳过并释放节点"。链表删除不需要移动元素，所以复杂度是O(n)，但要注意哨兵节点和头节点删除问题。

void removeAllX(Node *head, int x) { Node *prev = head; Node *curr = head->next; while (curr != NULL) { if (curr->val == x) { prev->next = curr->next; free(curr); curr = prev->next; } else { prev = curr; curr = curr->next; } } }

链表版本和顺序表版本最大的区别在于：链表删除是真正意义上的"拆节点"，不需要搬移元素；顺序表删除本质是"覆盖赋值"。你如果理解了这两个存储结构的本质差异，选择哪个结构作为删除操作的载体，一眼就能看明白。

5. 这道题最坑人的四个细节：我的实测踩坑记录

这部分是我自己刷题和帮别人review代码时积累的真实教训。写出来不是为了嘲笑当时的自己，而是帮大家少走弯路。

5.1 相邻x连续删除时，指针不自增的陷阱

逐个前移法里，我前面特别强调过else分支里的i++。很多初学者把写法浓缩成下面这样：

for (int i = 0; i < L.length; i++) { if (L.data[i] == x) { for (int j = i; j < L.length - 1; j++) { L.data[j] = L.data[j + 1]; } L.length--; } }

这个for循环在删除之后i会自动++，但对于连续x的情况，当前新位置还没有被检查就跳过去了。比如[1, 2, 2, 3]，删除第一个2后数组变成[1, 2, 3]，i从0变成1，下一次检查的其实是data[1]也就是原来的第二个2，但由于新的2已经占据位置0，i=1时检查的是位置1，这时它还是2吗？不是，数组变成[1,2,3]后位置1是2，还是会删。可是如果连续三个2，[1,2,2,2,3]删除i=1的2后变成[1,2,2,3]，i变为2，检查位置2，还是2，继续删除变成[1,2,3]，i变为3，检查位置3也就是原来的3，看起来也能删对。那为什么会漏删？关键在于删完后新的元素补到了i位置，如果执行完删除后i++，那么"从后面补到当前位置的元素"就没有被检查。反过来，如果执行删除后i不++，又要防止死循环，所以必须用while循环加else。

这就是为什么我建议直接抛弃这种写法，用双指针覆盖法。因为在双指针法里，i和k是两个独立变量，i只管往前探查，k只负责写，它们的语义被拆开了，就不会出现"当前位置被跳过"的问题。

5.2 长度同步问题：少改或不改length都会出大事

有个很现实的问题：删除过程中，如果你不维护length，下一次循环的终止条件就会基于错误长度。比如逐个前移法里，删除一个元素后length必须马上减一，否则for循环会把数组末尾残留的旧数据当成有效元素继续检查。我在一个模拟链表里debug了半天，最后发现不过是一个length漏减，引得后面所有逻辑全部混乱。

用双指针法时也要小心：遍历时用的是旧的length，遍历结束后再把length赋值为k。如果你在循环中途就把length改了，循环可能提前终止或者访问越界。所以最安全的写法是：循环条件始终基于原始表长，先完成遍历和写入，最后统一更新length。这一步的顺序错不得。

5.3 复杂度估算错误：不是所有写法都"差不多"

我看过不少同学做完之后说："反正考试数据量不大，O(n²)也能过。"这种心态在笔试里很危险。当表长从100涨到10000，O(n²)的时间会从毫秒级飙到秒级；如果平台还叠加其他操作，直接超时。

更重要的是，阅卷或面试官看的是你有没有复杂度意识。同样一道"删除所有x"，能写出双指针法的人，说明他心里有一杆秤：顺序表删除的本质是搬移，搬移次数越少越好。工程里这类"原地整理数组"的场景非常常见，比如清理日志、过滤无效数据，底层逻辑和这道题完全一致。你以为你只是在做习题，其实你在练一个工作后天天要用的基本功。

5.4 参数校验与不可变输入的问题

还有一个小细节：函数要不要检查传入的指针是否为空？表长是否为0？如果不检查，在某些判题系统里可能直接段错误。我个人习惯是：凡是C语言接口，默认调用方可能传NULL，所以必须在函数开头做防御性检查。这不是做题时才养成的习惯，而是工程代码的通用常识。

另一个容易被忽略的点是：如果原顺序表不允许修改，也就是const修饰，那就不能用双指针原地覆盖，必须另外开辟新表。新表做法的时间复杂度还是O(n)，但空间复杂度变为O(n)，这在面试时值得和面试官确认："题目是否允许原地修改？"因为这两个约束会导向不同解法。

最后分享一个我个人的小习惯。刷这类数组题时，我会刻意在草稿纸上画一条数轴，把i和k的移动过程画几轮，直到确信每一步都不会覆盖未读数据为止。顺序表删除所有x这道题，我第一次画出双指针走位图时，才真正理解k为什么永远不快于i——因为k指向的位置一定是已经被i检查过、被确定丢弃或者已经搬移区域的位置，它永远不会越过i去覆盖尚未处理的数据。这个"看穿"的感觉，比背代码要牢固得多。希望这篇文章能给你同样的体会。