大学第一次做这道“合并两个有序数组”我是真踩过坑的。当时图省事把两个顺序表拼到一起再调一趟排序交上去以为就完了。后来老师把代码打回来批了一句话“合并的目的是利用有序而不是恢复有序。”这句话我记了很多年。顺序表这个练习看起来简单但它真正要训练的是你能不能用双指针一趟走完把两个已经有序的序列合成一个新有序序列而不是靠排序兜底。这篇就把这个练习从头讲透题目到底在考什么、双指针是怎么推出来的、顺序表实现时有哪些内存和结构细节、C语言代码怎么写、以及去重、原地合并、集合并集这些变体怎么处理。适合正在学数据结构的学生也适合准备算法面试的人。1. 先搞清楚题目在考什么合并的有序性有多重要1.1 三种常见写法与背后的能力要求“合并两个有序数组”这个题网上能搜到三种典型写法。第一种就是我开头说的直接把两个数组的元素塞进一个新数组然后调qsort/Arrays.sort/Collections.sort。第二种是逐个元素比对把小的一端放进结果也就是双指针归并。第三种是进阶一点要求不借助额外数组直接把第二个数组合并进第一个数组里。这三种写法对应三种能力层次。第一种只能证明你“知道怎么把两组数据放一起”完全没有利用“有序”这个前提条件。它在时间上亏很大后面我会算具体账。第二种是这道题的核心它考的是归并思想的雏形两个有序序列各用一个指针谁小谁先进像两股溪流汇成一条河。这个思想往后会出现在归并排序、合并K个有序链表、多路归并外部排序等一堆地方。第三种考的则是空间意识和逆向思维——你不仅要会合并还要会“从后往前”合并避免覆盖未处理的元素。所以你在网上看到这个练习后面跟着一堆热搜词比如“java顺序表代码”“求解一般集合的并集问题的用顺序表实现完整c代码详解”“合并访存”“ffmpeg多个视频合并一个视频”其实都是同一类问题的不同壳子把多个有序数据源合成一路同时保证顺序不乱。顺序表练习只是把这个需求抽象成了最干净的一个模型。1.2 直接拼接再排序为什么是错误示范我先把第一种写法的时间账算给你听。假设第一个有序数组长度是 m第二个是 n。直接拼接再排序拼接本身的复杂度是 O(mn)排序一个长度为 mn 的数组常见排序算法平均是 O((mn)log(mn))。整体合计也是 O((mn)log(mn))。而双指针合并是 O(mn)。两个复杂度差在哪儿差在那项 log。mn 100 时log 那项还能接受mn 10 万时log 那项就要乘上十几。数据量越大差距越明显。更重要的是拼接再排序把“两个序列各自有序”这个信息完全丢掉了——你的算法没有“感知”到输入本身的规律这是算法学习里最忌讳的事。打个比方你手里是两摞已经按编号排好的档案现在要合成一摞。正常人会两个档案夹各拿一个指针谁编号小谁先放。你已经知道这两摞是排好的了却还把所有档案倒在地上重新按编号捡一遍那前面排序的人不就白干了吗双指针合并本质就是“让之前排序的工作继续起作用”。2. 双指针合并的完整推演从指针概念到每一步移动2.1 双指针法的基本框架双指针的思路可以用一句话概括在两个数组上各放一个指针分别指向当前还没被取出的最小元素每次比较这两个元素把较小的一个放进结果数组然后让对应的指针往后挪一位某一方的指针走到底之后把另一方剩下的元素全部追加到结果数组尾部。有人可能会问为什么比较的时候只看两个数组当前指针指向的元素就够了不用回头比已经放进结果的元素因为两个数组各自是有序的当前指针指向的已经是各自剩下元素里最小的。两个“当前最小”里更小的那一个自然就是全局剩余元素里最小的取它不会破坏结果的顺序。这是整个算法成立的基石理解这一点双指针就算学通了。通用的框架长这样初始化 i 0, j 0 开辟结果数组 result while i m 且 j n: 如果 a[i] b[j]把 a[i] 放进 resulti 否则把 b[j] 放进 resultj 循环结束后把剩余元素依次放进 result这里面“谁小谁进”写起来没什么难度真正容易出错的是循环结束后两个尾巴的收尾处理以及相等元素的走向。2.2 手推一遍看指针怎么走光看伪代码不够拿一组具体数据走一遍。设 a [1, 3, 5, 7]b [2, 4, 6]m 4n 3。初始 i 0j 0result 为空。第一步比较 a[0] 1 和 b[0] 21 更小把 1 放进 result。此时 i 变成 1j 还是 0。result [1]。第二步比较 a[1] 3 和 b[0] 22 更小把 2 放进 result。j 变成 1i 还是 1。result [1, 2]。第三步比较 a[1] 3 和 b[1] 43 更小放 3i 变 2。result [1, 2, 3]。第四步比较 a[2] 5 和 b[1] 44 更小放 4j 变 2。result [1, 2, 3, 4]。第五步比较 a[2] 5 和 b[2] 65 更小放 5i 变 3。result [1, 2, 3, 4, 5]。第六步比较 a[3] 7 和 b[2] 66 更小放 6j 变 3。此时 j 已经等于 nb 数组的元素取完了。第七步进入收尾循环i 还没走到头把 a[3] 7 追加进去。最终 result [1, 2, 3, 4, 5, 6, 7]。注意观察每一步放进 result 的元素都是当时两个指针能看到的元素里最小的。指针只往前走从不回头总共走了 mn 步这个特性决定了算法的复杂度。2.3 相等元素的处理策略相等元素是这个练习里面最容易扯皮的地方。a [1, 2, 2, 5]b [2, 2, 6]合并之后到底该有多少个 2标准合并比如 LeetCode 88 题那种场景默认两个相等的都保留。因为有序数组可以包含重复元素合并后仍然允许重复保持非递减序即可。写法上就看你想让相等时取左还是取右两个都行只要别漏掉或者死循环。如果要实现集合并集那就是另一套规则相等的元素只保留一个。比如“求解一般集合的并集问题”里集合的互异性要求重复元素只出现一次。这种情况需要在合并的同时去重代码会在第 4.2 节给出记住一个核心技巧往 result 里放元素之前先判断 result 是否为空、当前元素和 result 最后一个元素是否相等相等则跳过。还有第三种情况是题目明确“去重合并”但要求你直接在原数组上操作。这种组合我建议你直接放弃原地思路用新建数组 去重判断来完成。原因后面讲原地合并的时候会说明。3. 顺序表实现中的内存与结构细节3.1 为什么这个题用顺序表而不是链表这个练习的题目名称就叫“顺序表的练习”数据结构被指定为顺序表。但深入了解之后会发现这个选择不是随便定的。顺序表的底层是连续数组data[i]的访问是 O(1)。双指针合并每轮都要随机访问两个数组的当前下标顺序表能直接通过下标定位。链表的话虽然也能用两个指针往前走但取第 i 个元素需要从头遍历复杂度差出一截而且你要为合并结果额外维护指针域代码结构复杂很多。另外顺序表的所有元素在内存中是连续存放的。合并时按顺序写入结果数组写入位置连续缓存命中率比链表高很多。你可能觉得这个练习的量级小感觉不到差异但换成几百万条记录的外部归并场景这差距就是秒级和分钟级的区别。所以顺序表这个载体和双指针合并算法是天然匹配的。算法依赖随机访问顺序表提供随机访问算法连续写入顺序表连续存储。这也是大多数教材把这个练习安排在顺序表章节的原因。3.2 新建结果表的容量规划写合并函数前要先想清楚结果表怎么建。最省事的写法是初始化一个空顺序表容量给个初始值然后用push_back逐个插入满了就扩容。这种写法代码简单适合当作练习演示因为每个元素都走统一的插入逻辑。但细想一下合并前我们已经知道结果的长度。两个表长度分别是 m 和 n合并结果长度就是 mn去重场景是 mn。既然长度已知完全可以一次性把容量设成m n让底层malloc直接分配足够空间省掉扩容这一层。更优雅的写法是封装一个create_seqlist_with_capacity(m n)或者直接在结构体里预留 capacity 字段初始化结果表时capacity m n。这样既不用realloc也避免了“明明知道要存多少却还要一点点试探着扩”的尴尬。在真实工程里一次性预分配还能减少内存碎片这是很多线上服务在批量导入数据时采用的做法。手动扩容和预分配各有适用场景。如果你写的是通用合并函数输入数组长度不确定就用预分配两个数组合并后的最大长度如果你写的是通用顺序表库的push_back那就保留动态扩容。两者并不矛盾关键是你要意识到这个题目里长度是已知的不提前预分配就是自己给自己制造无意义的扩容开销。3.3 原地合并版本从后往前填的妙处有些面试题会把场景改成第一个数组长度是 mn前 m 个是有效元素后 n 个是空的通常用 0 占位要求把第二个数组合并进第一个数组不使用额外数组。这是 LeetCode 88 题的原型。很多人的第一反应是“从前开始填”。但从前填有个致命问题当你把 nums1[0] 覆盖成更小的值时原来存在 nums1[0] 的元素可能还没被比较过直接丢了。标准解法是从后往前填。逻辑是用 p 指向 nums1 有效区末尾q 指向 nums2 末尾index 指向 nums1 总长度的末尾。从后往前比较把更大的元素放到 index 位置然后 index 和对应的指针一起往前移。因为后面的位置一开始是空的我们往空位置写值永远不会覆盖还没处理的元素。我拿个例子走一下。nums1 [1, 2, 3, 0, 0, 0]m 3nums2 [2, 5, 6]n 3。p 2q 2index 5。比较 nums1[2] 3 和 nums2[2] 66 更大nums1[5] 6q 1index 4。比较 3 和 55 更大nums1[4] 5q 0index 3。比较 3 和 23 更大nums1[3] 3p 1index 2。比较 nums1[1] 2 和 nums2[0] 2相等按标准合并两个都保留。取 nums1 的 2nums1[2] 2p 0index 1。比较 nums1[0] 1 和 nums2[0] 21 更小nums1[1] 1p -1index 0。p 已经越界把 nums2 剩余的元素写入nums1[0] 2。最终 nums1 [1, 2, 2, 3, 5, 6]。结果正确。从这里也能看出原地版本为什么不适合去重需求它假定目标区域长度恰好是 mn即重复元素也要占一个位置一旦要求去重目标区域长度就变成 mn用这个固定长度的结构去承接“可变数量”的元素位置管理会很别扭。需要去重时老老实实新建数组加一个“当前元素是否等于 result 最后一个元素”的判断简单又可靠。4. 完整C语言代码与测试过程4.1 顺序表的结构定义与基础操作先把顺序表的结构体定义出来尽量贴近教材习惯的写法#include stdio.h #include stdlib.h #define INIT_CAPACITY 8 typedef struct { int *data; int length; int capacity; } SeqList;这里data是底层数组指针length是当前元素个数capacity是已分配容量。接下来是初始化、插入和释放三个基础操作void init_seqlist(SeqList *list) { list-data (int *)malloc(sizeof(int) * INIT_CAPACITY); if (list-data NULL) { printf(内存分配失败\n); exit(1); } list-length 0; list-capacity INIT_CAPACITY; } void push_back(SeqList *list, int val) { if (list-length list-capacity) { list-capacity * 2; list-data (int *)realloc(list-data, sizeof(int) * list-capacity); if (list-data NULL) { printf(扩容失败\n); exit(1); } } list-data[list-length] val; list-length; } void destroy_seqlist(SeqList *list) { free(list-data); list-data NULL; list-length 0; list-capacity 0; }讲解一下push_back里为什么要判断length capacity顺序表是连续数组插入前必须先确认空间。空间满了就扩容这里采用倍增策略容量直接乘 2因为一次扩容多分配一点可以减少 realloc 的调用次数平均插入代价摊销下来接近 O(1)。如果每次只扩一个位置插入 n 个元素就会 realloc n 次性能会很难看。提示realloc失败时返回 NULL而原来的内存块仍然有效。这里直接把它赋给list-data会导致原来的指针丢失严格写应该用一个临时变量接收返回值判断成功后再赋回。教学代码里为了简洁可以直接处理但你心里要知道这个细节。4.2 merge函数实现标准合并与去重合并两个版本标准合并对应“合并两个有序数组保留重复元素”SeqList merge(const SeqList *a, const SeqList *b) { SeqList result; result.data (int *)malloc(sizeof(int) * (a-length b-length)); if (result.data NULL) { printf(内存分配失败\n); exit(1); } result.length 0; result.capacity a-length b-length; int i 0, j 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { result.data[result.length] a-data[i]; i; } else { result.data[result.length] b-data[j]; j; } } while (i a-length) { result.data[result.length] a-data[i]; i; } while (j b-length) { result.data[result.length] b-data[j]; j; } return result; }注意这段代码里我用的是a[i] b[j]相等时走 else 分支也就是从 b 取。这只是一种约定结果没有区别因为两个相等的元素谁先谁后并不影响最终的有序性。接下来是去重合并对应“集合并集”场景SeqList merge_unique(const SeqList *a, const SeqList *b) { SeqList result; result.data (int *)malloc(sizeof(int) * (a-length b-length)); if (result.data NULL) { printf(内存分配失败\n); exit(1); } result.length 0; result.capacity a-length b-length; int i 0, j 0; while (i a-length j b-length) { int val; if (a-data[i] b-data[j]) { val a-data[i]; i; } else if (a-data[i] b-data[j]) { val b-data[j]; j; } else { val a-data[i]; i; j; } if (result.length 0 || result.data[result.length - 1] ! val) { result.data[result.length] val; } } while (i a-length) { int val a-data[i]; i; if (result.length 0 || result.data[result.length - 1] ! val) { result.data[result.length] val; } } while (j b-length) { int val b-data[j]; j; if (result.length 0 || result.data[result.length - 1] ! val) { result.data[result.length] val; } } return result; }去重逻辑在这里只用一个判断result.data[result.length - 1] ! val。为什么能这样简化因为两个输入数组各自有序合并过程也是单调递增地把元素放进去所以相等的元素一定连续出现不可能隔着一个更小的值再冒出来一个相同值。只要和已放入的最后一个元素比较就够了不需要 O(n) 地去历史数组里查重。4.3 测试用例设计与运行结果写完函数不能直接拿出去用设计几个有代表性的测试用例一个空数组、一个非空数组两个数组长度差距大有重复元素的数组完全交错的两个数组第一个数组所有元素都小于第二个数组main 函数示例void print_seqlist(const SeqList *list) { for (int i 0; i list-length; i) { printf(%d , list-data[i]); } printf(\n); } int main() { SeqList a, b; int arr1[] {1, 3, 5, 5, 7}; int arr2[] {2, 4, 5, 6, 8, 9}; init_seqlist(a); init_seqlist(b); for (int i 0; i 5; i) push_back(a, arr1[i]); for (int i 0; i 6; i) push_back(b, arr2[i]); SeqList r1 merge(a, b); printf(标准合并结果: ); print_seqlist(r1); SeqList r2 merge_unique(a, b); printf(去重合并结果: ); print_seqlist(r2); destroy_seqlist(a); destroy_seqlist(b); destroy_seqlist(r1); destroy_seqlist(r2); return 0; }运行输出标准合并结果: 1 2 3 4 5 5 5 6 7 8 9 去重合并结果: 1 2 3 4 5 6 7 8 9标准合并里出现了三个 5因为 a 里有两个 5b 里有一个 5合并后全部保留。去重合并只剩一个 5符合集合并集的语义。测试用例里故意让两个数组都有 5就是为了验证相等元素的处理是否符合预期。4.4 Java实现的简略版热度词里出现了“java顺序表代码”也顺手给一个 Java 版本。思路一模一样区别在于 Java 用ArrayList或者原生数组都行。原生数组版本最简单public static int[] merge(int[] a, int[] b) { int[] res new int[a.length b.length]; int i 0, j 0, k 0; while (i a.length j b.length) { if (a[i] b[j]) { res[k] a[i]; } else { res[k] b[j]; } } while (i a.length) { res[k] a[i]; } while (j b.length) { res[k] b[j]; } return res; }去重版本只需要在写入前加一个判断if (k 0 || res[k - 1] ! val)。Java 里很多人会用ArrayListInteger再转数组但面试时优先用原生数组原因很简单不涉及装箱拆箱代码清爽也方便直接分析复杂度。5. 复杂度分析、变体延伸与踩坑盘点5.1 时间和空间复杂度到底怎么算时间复杂度主循环里每次至少让 i 或 j 前进一个位置总共前进 mn 次。两个收尾循环合起来最多也是 mn 次。所以总时间严格是 O(mn)。这不是估算而是每一步都有实际推进属于线性算法。空间复杂度要看合并策略。新建数组版本额外分配了 mn 的位置是 O(mn)。原地合并版本只用了几个指针变量额外空间是 O(1)。去重合并版本最坏情况仍然分配了 mn 个位置但实际使用不超过 mn所以也是 O(mn)。一个容易混淆的点很多人会把“结果数组”算进空间复杂度。如果题目中“合并”指的就是返回一个新的有序数组那结果数组是输出的一部分不算额外空间。只有“在原数组上合并不允许开新数组”的题目才要求空间复杂度 O(1)。算法题里约定俗成返回值占的空间一般不算额外空间这一点刷题时一定看清题目描述。5.2 把合并问题推广到集合并集热度词里“求解一般集合的并集问题的用顺序表实现完整c代码详解”就是本题去重合并的同义表达。一般的集合并集问题输入是两个无序集合要求输出它们的并集。但顺序表通常只保证存储顺序不保证元素有序所以单纯的连接再遍历可以用效率一般。实践中处理无序集合并集的常规做法有先排序再合并排序成本 O((mn)log(mn))合并成本 O(mn)哈希法把一个集合的元素放入哈希表遍历另一个集合往里放代价近似 O(mn)但需要额外哈希表空间如果两个集合本身已经有序就用本文的合并去重函数线性完成这里有个工程判断值得说不要迷信哈希法永远最优。当元素是简单整数且数据量不大时先排序再合并往往更快因为排序是内存连续读写哈希表有额外的散列和冲突处理开销。我在实际项目里合并上百万个 ID 时对比过双指针合并比哈希法稳定快出一个量级。数据特征决定方案选择没有银弹。5.3 与归并排序的关系以及面试延伸这个练习的 merge 函数其实就是归并排序最核心的 merge 步骤。归并排序的思路是把数组不断二等分分到只剩一个元素然后两两合并合并时用到的就是本文的这段双指针代码。很多人学归并排序时觉得难其实拆开看前半部分是递归切分后半部分就是今天这个练习题。先把合并两个有序数组吃透归并排序的代码就能默写出来。顺着这个方向还可以延伸出三个常见变体合并 K 个有序数组。两个数组用双指针K 个数组不能再用两个指针硬扫最小堆是标准解法把每个数组当前的最小元素扔进堆弹出最小的放进结果然后从对应数组补下一个。复杂度 O(KN log K)N 是每个数组的平均长度。原地合并数组。就是我前面讲的 LeetCode 88从后往前填。只求第 K 小的元素。不用完整合并每次比较两个指针位置跳过小的那批二分确定每次跳过的数量复杂度能优化到 O(log(mn))。这属于进阶玩法面试里出现率不低。5.4 实操中容易踩的坑最后盘点一下我见过和踩过的高频坑希望你别再走一遍。第一个坑循环收尾忘写。主循环结束后两个数组可能都有剩余也可能只有一边有。很多人写完主循环就 return等于把尾巴丢了一半。标准做法是写两个 while 收尾一个处理 a 剩余一个处理 b 剩余绝不嫌多。第二个坑容量和长度混淆。顺序表里length和capacity是两回事我见过不少新人把result.capacity当成元素个数去遍历结果越界读出一堆垃圾值。记住遍历一律看lengthcapacity只是分配的上限。第三个坑realloc失败导致原指针丢失。严格写法是先存临时变量成功后再赋值。教学代码里很多人直接list-data realloc(...)卡在极端内存场景会泄漏。养成用临时变量的习惯不亏。第四个坑去重时用了哈希集合而不是单变量判断。有人不管数据有序无序一律建哈希表去重结果是代码复杂、内存翻倍、速度更慢。遇到“两个有序数组求并集”检查“最后一个元素是否相等”就已经够用这是有序给你的特权。第五个坑原地合并从前往后填。已经讲过了覆盖未处理元素的错误非常隐蔽跑小数据可能碰巧没出事换一组数据就崩。记住口诀有额外空间就新建数组没额外空间就倒着填。我自己后来在项目里处理跨表合并报表、多路日志归并回头再看这个练习才发现当初老师那一句评语有多值钱。合并两个有序数组不是一个孤立的小题它是“把有序信息传递下去”这一思想的第一次正式训练。把这一趟双指针走明白后面归并排序、K路归并、甚至数据库里的归并连接你都会觉得眼熟。