到O(n)的双指针原地覆盖)
第二章-线性表 大题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]x3遍历位置i当前元素是否保留写入位置k数组现场只看前k个有效03否0暂无保留17是0→1[7]23否1[7]33否1[7]49是1→2[7, 9]53否2[7, 9]61是2→3[7, 9, 1]73否3[7, 9, 1]83否3[7, 9, 1]95是3→4[7, 9, 1, 5]遍历结束后k4所以新表长度就是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 这个关系始终成立因为每遇到一个xk就比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::vectorint 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 十个容易被忽视的边界场景做题时大部分人只测一个普通用例就收工这是最要命的。我列一份比较完整的测试场景表你写完代码后照着跑一遍基本上就能杜绝低错。场景示例预期结果容易出现的问题空表[]长度仍为0忘记处理但一般不会崩表里全是x[5,5,5]长度变为0逐个前移法这里会退化成O(n²)表里没有x[1,2,3]原样不变最终k应该等于nlength不能丢x在开头[5,1,2][1,2]漏掉首元素后忘了处理x在结尾[1,2,5][1,2]尾元素处理不当length多1连续多个x[1,5,5,2][1,2]删除后i不自增会漏删第二个5x交替出现[5,1,5,2,5][1,2]双指针法仍能正确保留单元素表且等于x[5]长度0length与data的同步问题单元素表且不等于x[1]长度1基本不会有问题极大表长接近MAXSIZE长度99删到几乎为空长度正确MAXSIZE不是length注意区分容量与长度我特别想强调表里全是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已经占据位置0i1时检查的是位置1这时它还是2吗不是数组变成[1,2,3]后位置1是2还是会删。可是如果连续三个2[1,2,2,2,3]删除i1的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涨到10000O(n²)的时间会从毫秒级飙到秒级如果平台还叠加其他操作直接超时。更重要的是阅卷或面试官看的是你有没有复杂度意识。同样一道删除所有x能写出双指针法的人说明他心里有一杆秤顺序表删除的本质是搬移搬移次数越少越好。工程里这类原地整理数组的场景非常常见比如清理日志、过滤无效数据底层逻辑和这道题完全一致。你以为你只是在做习题其实你在练一个工作后天天要用的基本功。5.4 参数校验与不可变输入的问题还有一个小细节函数要不要检查传入的指针是否为空表长是否为0如果不检查在某些判题系统里可能直接段错误。我个人习惯是凡是C语言接口默认调用方可能传NULL所以必须在函数开头做防御性检查。这不是做题时才养成的习惯而是工程代码的通用常识。另一个容易被忽略的点是如果原顺序表不允许修改也就是const修饰那就不能用双指针原地覆盖必须另外开辟新表。新表做法的时间复杂度还是O(n)但空间复杂度变为O(n)这在面试时值得和面试官确认题目是否允许原地修改因为这两个约束会导向不同解法。最后分享一个我个人的小习惯。刷这类数组题时我会刻意在草稿纸上画一条数轴把i和k的移动过程画几轮直到确信每一步都不会覆盖未读数据为止。顺序表删除所有x这道题我第一次画出双指针走位图时才真正理解k为什么永远不快于i——因为k指向的位置一定是已经被i检查过、被确定丢弃或者已经搬移区域的位置它永远不会越过i去覆盖尚未处理的数据。这个看穿的感觉比背代码要牢固得多。希望这篇文章能给你同样的体会。
