看到这个标题我第一反应是想起上周代码评审时吵起来的一个场景两个同事为了一个“把两个接口返回的ID列表合并、去重、排序再展示”的需求一个写了三重循环逐项比对去重另一个先合并、再排序、最后相邻元素去重两个人在白板上画了两版方案谁都不服谁。其实这个需求翻译成算法题就是标题这行字——合并两个有重复元素的无序数组返回无重复的有序结果。这题目看起来简单但它同时考了三个基本功合并操作、去重逻辑、排序选择还牵涉到不同数据规模下的性能取舍。这篇文章我打算从需求拆解讲到多语言实现再延伸到链表版本最后把实际开发中踩过的坑拿出来晒一晒。适合正在刷题备考的读者、写业务代码想提升代码质量的开发者以及对数组和链表底层逻辑感兴趣的初学者。1. 先拆需求无序、重复、有序这三个词各自代表什么考点1.1 “无序”决定了你不能无脑用双指针合并很多人在看到“合并两个数组”时第一反应是套用有序数组合并的双指针模板两个指针分别指向数组头部谁小谁进结果数组一趟遍历 O(nm) 结束。这个模板本身没错但它有一个严格前提——两个输入数组都已经是有序的。题目特意强调“无序”就是为了堵死这条捷径。一旦数组无序你只有两条路要么先把数组排序再走双指针要么放弃双指针改用哈希表等结构直接去重。前者的开销是 O(n log n) 的排序后者则需要额外空间存哈希表。换句话说“无序”这两个字已经把题目基调定死了这道题真正想考的其实是“排序”和“去重”这两项能力合并只是搭了个台子。面试时如果你一开始就写双指针写到一半发现要补排序反而会在思维上绕一个大弯。提示审题时先看输入是否有序这是一个极易被忽视的考点。无序数组的合并核心难点从来不在“合并”本身而在于你打算用哪种方式让结果有序且唯一。1.2 “重复元素”其实有三种来源去重必须一次覆盖两个数组里的重复元素来自三个地方数组 A 自身内部的重复、数组 B 自身内部的重复、以及 A 和 B 交叉部分的重复。举一组数据A [1, 1, 2, 4]B [2, 3, 4, 4]。A 内部有一个重复的 1B 内部有一个重复的 4A 和 B 之间又有重复的 2 和 4。如果你去重的逻辑只考虑“两个数组之间的重复”就一定会漏掉数组内部重复的情况。重复来源示例处理方式A 内部重复A [1, 1, 2]只保留一个 1B 内部重复B [4, 4, 5]只保留一个 4A 与 B 交叉重复A [2], B [2, 3]合并后只保留一个 2正确的思路是先合并再把合并后的大数组当作一个整体去重。这样三种来源的重复一次性全部处理掉不需要对每个数组单独去重。反过来如果你先对 A 去重、再对 B 去重、最后再去一次交叉重复代码会变成三套相似逻辑既啰嗦又容易出错。我在 code review 里见过不少这种“三步去重”的写法基本都会在交叉重复这一步漏掉边界情况。1.3 “有序结果”还藏着排序规则和稳定性的问题题目只说“返回有序结果”没说升序还是降序也没说按什么规则排序。算法题里默认是数字按数值升序但真实业务中“有序”的定义往往需要跟产品确认。同样是“列表排序”价格从低到高和销量从高到低是两个完全相反的方向字符串列表可以是按字典序也可以按长度排对象数组还得指定按哪个字段排。还有一个容易忽略的点如果数组里存的是对象两条记录 id 相同但其他字段不同去重时应该保留哪一条比较稳妥的约定是“保留第一次出现的元素”这在用 Set 时天然成立——Set 在底层哈希表中只记录第一次插入的键后续重复值会被忽略。但如果你用“先排序再去重”的方案排序过程可能会把原本靠前的记录挪到后面相当于改变了“谁先出现”的语义。所以在题目没明确说明时优先选择能保留首次出现的方案至少不会产生歧义。2. 三种解法选型集合去重、排序后去重、哈希计数怎么选2.1 方案一Set 集合去重加排序代码最简单Set 的核心特性是元素唯一性底层是哈希表插入和查找平均 O(1)。这个方案的核心思路是先合并两个数组把合并结果直接丢进 Set让 Set 完成去重再把它转回数组排序。顺序无所谓因为排序在去重之后执行不会影响去重结果。JavaScript 写起来可以一行const result [...new Set([...arr1, ...arr2])].sort((a, b) a - b);如果你不想用展开运算符也可以用 concatconst merged arr1.concat(arr2); const result Array.from(new Set(merged)).sort((a, b) a - b);Python 更短但有个细节需要小心后面章节会专门讲result sorted(set(arr1 arr2))这个方案最大的优点是可读性高逻辑完全自解释。我先合并再去重最后排序每一步都对应题目需求。对于绝大多数开发场景这就是最优解——你不需要为了“看起来更底层”而牺牲代码清晰度。2.2 方案二合并后排序再相邻去重省内存有些语言没有内置 Set或者面试官明确要求不能用额外空间那就必须走排序去重这条路先把两个数组合并到一个大数组整体排序然后利用“排序后重复元素必然相邻”的性质一次遍历把重复项剔除。C 里最经典的三件套vectorint nums; nums.insert(nums.end(), arr1.begin(), arr1.end()); nums.insert(nums.end(), arr2.begin(), arr2.end()); sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end());这里的核心是unique函数。它只能去掉连续相邻的重复元素所以必须在排序之后调用。如果数组还没排序两个相同的元素隔着十万八千里unique一个都去不掉。这个“先排序再相邻去重”的思路也能手写实现int k 0; for (int i 0; i nums.size(); i) { if (i 0 || nums[i] ! nums[k - 1]) { nums[k] nums[i]; } } nums.resize(k);方案二的优势是空间占用极小。排序是原地算法去重也在原数组上完成额外空间几乎为零。这在嵌入式开发、内存受限的系统中非常关键。2.3 方案三哈希表计数需要统计频次时的升级版如果只是“去重排序”用哈希表计数确实有点杀鸡用牛刀。但它的价值在于当题目进阶成“返回出现频率最高的前 K 个元素”“统计每个元素出现次数”时哈希计数是唯一的直接解法。有了这一步等于把这道题和 TopK、频次统计等更高频的考点打通了。Python 写法from collections import Counter merged arr1 arr2 counter Counter(merged) result sorted(counter.keys())Java 用 Map 计数也类似。本质是利用哈希表的键保证唯一性同时用值记录出现次数。排序时对 key 排序即可。2.4 三种方案的横向对比和选择建议方案实现思路时间复杂度额外空间是否保留首次出现适用场景Set 去重加排序哈希去重再排序O(n log n)O(n)是通用场景首选排序后相邻去重排序再原地去除相邻重复O(n log n)可做到 O(1)否顺序被排序改变内存受限、无集合类型哈希计数统计频次取 key 排序O(n log n)O(n)是需要频次信息的进阶需求我给团队定的选择逻辑很简单平时业务代码首选 Set 方案因为人对可读性的收益远大于那点性能差距。只有在明确要做大规模数据合并、或者运行环境内存极小时才降级到排序后去重方案。3. 多语言落地JS、Python、Java、C 的写法和差异3.1 JavaScript一行代码背后有两个坑JS 最优雅的写法就是 Set 加 sort 的组合const mergeUniqueSorted (a, b) { return [...new Set([...a, ...b])].sort((x, y) x - y); };第一个坑是 sort 的默认排序规则。JS 的 Array.prototype.sort 在没有传入比较函数时会把所有元素转成字符串按字典序排序。[1, 2, 10].sort()的结果不是[1, 2, 10]而是[1, 10, 2]因为字符串 “10” 排在 “2” 前面。这个坑几乎每个 JS 开发者都踩过。今天的题目里如果只写.sort()不写比较函数数据里一旦出现两位数就翻车。第二个坑是展开运算符的内存峰值。[...a, ...b]这步会先创建一个新数组长度等于 a 和 b 的长度之和意味着多一次完整的大数组拷贝。两个数组各有 20 万条数据时这一步可能直接导致内存飙升。我在后面第 6 章会讲一个线上真实事故。// 更稳的写法 const set new Set(arr1); for (let i 0; i arr2.length; i) { set.add(arr2[i]); } const result Array.from(set).sort((x, y) x - y);3.2 Python最优雅但别忽略 set 的遍历顺序Python 常规解法def merge_unique_sorted(arr1, arr2): return sorted(set(arr1 arr2))但注意两个细节。第一arr1 arr2会先构造一个完整的大列表如果数组很大这一步会带来额外内存开销。稳妥写法是def merge_unique_sorted(arr1, arr2): s set(arr1) s.update(arr2) return sorted(s)第二set 的遍历顺序是不保证的。Python 的 dict 从 3.7 起保证插入顺序但 set 从来没有这个保证。CPython 的 set 内部基于哈希表遍历顺序与哈希值、容量、插入历史都有关系所以绝不能写list(set(...))后不排序就当成有序结果。题目要求最终有序排序这一步无论如何都不能省。3.3 JavaHashSet、TreeSet、Stream 三种路线Java 手写集合类版本Integer[] arr1 {3, 1, 2, 2}; Integer[] arr2 {4, 3, 1, 5}; // 方式一HashSet Collections.sort SetInteger set new HashSet(); Collections.addAll(set, arr1); Collections.addAll(set, arr2); ListInteger list new ArrayList(set); Collections.sort(list); // 方式二TreeSet 自动排序 TreeSetInteger treeSet new TreeSet(); Collections.addAll(treeSet, arr1); Collections.addAll(treeSet, arr2); Integer[] result treeSet.toArray(new Integer[0]); // 方式三Stream 一行流 int[] result Stream.concat( Arrays.stream(arr1), Arrays.stream(arr2) ).distinct().sorted() .mapToInt(Integer::intValue).toArray();方式二是 TreeSet底层是红黑树插入时自动保持有序。但要注意TreeSet 每次插入是 O(log n)和“HashSet 插入 O(1) 后整体排序 O(n log n)”相比总复杂度一致常数通常更大。方式三 Stream 最声明式但如果你操作的是基本类型数组int[]Arrays.stream得到的是IntStream不是StreamInteger拼合时类型容易混。这里务必区分清楚。3.4 C/C没有现成集合时的完整手写流程C 语言没有 Set 类型最直观的做法就是方案二合并、qsort、原地去重。#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { int x *(int *)a, y *(int *)b; return (x y) - (x y); } int* merge_unique(int *a, int na, int *b, int nb, int *ret_size) { int total na nb; int *nums (int *)malloc(total * sizeof(int)); for (int i 0; i na; i) nums[i] a[i]; for (int i 0; i nb; i) nums[na i] b[i]; qsort(nums, total, sizeof(int), cmp); int k 0; for (int i 0; i total; i) { if (i 0 || nums[i] ! nums[k - 1]) { nums[k] nums[i]; } } *ret_size k; return nums; }一个容易被追问的细节是 cmp 函数的写法。如果你写return *(int *)a - *(int *)b;当两个 int 的差值超出 int 范围时会溢出比如INT_MAX - (-1)就已经越界可能导致排序结果错误。用(x y) - (x y)这种写法就永远安全它只返回 -1、0、1 三种结果。C 有两个升级选择。一是 STL 三件套sort unique erase二是直接用std::set接收合并结果再拷贝到 vector。两者都行但前者省内存后者代码更少。4. 从数组延伸到链表无序链表合并去重的完整处理思路4.1 为什么这个题目会自动联想到链表标题里写了“数组/链表操作”说明出题人希望你在掌握数组解法后还能把“合并、去重、排序”这三个动作迁移到链表数据结构上。链表和数组的最大区别是链表不能随机访问没有索引排序不能直接用快排的数组版本去重也不能靠nums[k]原地覆盖。所以链表版本更像一道操作题考察的是指针连接、节点删除、以及边界节点的处理。4.2 思路一哈希集合标记加原地链表删除先考虑一个不需要排序的路线用哈希集合记录已经出现过的值遍历一次链表遇到重复节点就删除。这种写法的时间复杂度是 O(n)而且不改变链表原有顺序。伪代码如下seen empty hash set prev null cur head while cur: if cur.val in seen: prev.next cur.next free(cur) cur prev.next else: seen.add(cur.val) prev cur cur cur.next但这只是完成了“合并后去重”还没解决“有序”的问题。如果题目要求最终返回有序链表那还得单独对链表做一次排序。换句话说这条思路把问题拆成了“先去重、再排序”适合面试时先说思路再逐步实现。4.3 思路二合并后排序再去重用归并排序垫底链表排序最稳妥的是归并排序因为它只需要 O(log n) 的递归栈空间而且对链表这种不支持随机访问的结构非常友好。整体流程完整版先把两个链表合并成一个链表。如果只是想合并逻辑节点可以不用新建节点直接把第二个链表的头节点接到第一个链表的尾节点。用快慢指针找到链表中点把链表切成两半。递归对左右两半分别排序。用合并两个有序链表的套路双指针比较节点大小把左右两半合并起来。链表整体有序后从头遍历一次发现相邻节点值相同就删除后一个节点。实现链表排序的递归核心struct Node* sortList(struct Node* head) { if (!head || !head-next) return head; // 快慢指针找中点 struct Node *slow head, *fast head-next; while (fast fast-next) { slow slow-next; fast fast-next-next; } struct Node* mid slow-next; slow-next NULL; struct Node* left sortList(head); struct Node* right sortList(mid); return mergeTwoLists(left, right); }4.4 链表指针操作的三个高频错误链表版最容易出三个问题而且基本都是指针操作细节第一删除重复节点后prev的 next 没有正确指向被删节点的后继导致链表断掉或出现悬空指针。第二没有使用哨兵节点。当链表的头节点就是重复节点时如果你直接操作head会丢失整个链表的入口。统一做法是创建一个 dummy 节点让dummy-next head最终返回dummy-next。第三合并两个有序链表时比较完大小后忘记移动对应指针造成死循环代码在链表很长时会直接卡死。提示链表题所有涉及“可能删除头节点”的场景一律先建哨兵节点这是最稳的防御姿势。5. 复杂度分析与实测数据规模变了结论就得变5.1 三种方案的时间和空间复杂度完整对比设两个数组长度分别为 n 和 mN n m。方案合并去重排序总时间复杂度额外空间Set 去重加排序O(nm)O(N) 平均O(N log N)O(N log N)O(N)排序后相邻去重O(nm)O(N)O(N log N)O(N log N)O(1)哈希计数O(nm)O(N)O(N log N)O(N log N)O(N)从大 O 看三种方案没有本质区别。但常数因子和实际性能差别很大。Set 方案里哈希表的插入涉及哈希计算、扩容和 rehash常数最大排序后去重方案靠的是快速排序常数相对小哈希计数方案比 Set 多一次“更新频次”的操作。5.2 小数据量下的实测结论当 N 小于 1000 时什么方案都是毫秒级甚至双层循环暴力去重也就几毫秒。这时候纠结性能没有意义挑可读性最好的方案就行。我自己写业务代码时小于一万条的数据从来不优化因为代码写得清晰比省下两毫秒重要得多。5.3 大数据量下的实测结论N 到 10 万以上方案差异开始显现。有几个经验性的规律元素越离散哈希表方案优势越明显因为它能把 O(N log N) 的排序几乎压到 O(N log N) 里的 log N 部分也可能被哈希表“稀释”元素越密集即重复率越高Set 维护的元素数量就越小内存优势越明显。反过来如果内存非常吃紧比如涉及嵌入式环境或超大文件处理排序后去重方案几乎是唯一选择——它把额外空间压到 O(1)代价只是多花一点排序时间。5.4 一个简单粗暴的方案选择口诀现在团队里的新人问我怎么选我都让他们背三句话内存不缺、追求可读性就选 Set 去重再排序内存敏感、语言没有集合类型就选排序后相邻去重后续要统计频次或者做 TopK就选哈希计数。这三句话基本覆盖日常所有场景。6. 边界条件与排错实录这些坑我几乎都踩过6.1 空数组和空指针从来不是小事两个数组都为空时应该返回空结果而不是报错。一个为空另一个正常返回去重后的结果。用 JS 或者 Java 这类语言时还容易忽略数组为 null 的情况。函数开头先做防御性判断是最成熟的做法if (!arr1 || !arr2) return [];很多人在写 LeetCode 风格的代码时觉得判空多余但真实业务里接口返回的数组经常为空或者直接返回 null。函数入口不做防御后面一旦取arr1.length就直接抛异常。这个习惯要养成。6.2 全是重复元素的退化场景当两个数组的所有元素都一样比如[7, 7, 7]和[7, 7, 7, 7]去重后应该得到一个[7]。这种极端的退化场景很容易暴露逻辑漏洞。比如排序后去重的循环如果你用nums[i] nums[i1]来判断是否重复等于把最后一个元素孤立在外面如果条件写成nums[i] nums[i-1]又不处理 i0 的情况就会越界。我建议调试任何去重算法时先拿一组全重复数据跑一遍检查结果长度是否正确。6.3 JavaScript sort 默认字典序的经典陷阱这个坑我在 code review 里见过至少三次。有人写const arr [1, 21, 3, 11]; arr.sort(); console.log(arr); // [1, 11, 21, 3]原因在于 sort() 未传比较函数时会把元素全部转成字符串按 Unicode 码点排序。字符串 “21” 和 “3” 比较时“2” 比 “3” 小所以 21 排在 3 前面。题目要求“有序结果”时你只写.sort()不加(a, b) a - b两位数一出现结果就是错的。这个坑在 JS 里几乎无解只能通过习惯性写比较函数规避。6.4 一个真实排错过程展开运算符让页面卡死了前阵子一个后台系统要做两个接口返回 ID 列表的合并展示我一开始写的正是最简洁的一行版const result [...new Set([...a, ...b])].sort((x, y) x - y);本地测试 1000 条数据毫无压力到测试环境后两个接口分别返回 20 万条 ID页面差点卡到失去响应。排查链路是这样的先打开浏览器 Network 面板确认接口返回本身没有变慢时间几乎全花在前端脚本执行上。在控制台手动分段打点发现最慢的一步是[...a, ...b]展开操作而不是排序。用 Performance 记录内存曲线看到展开操作的瞬间内存峰值飙升之后反复触发垃圾回收导致页面被 GC 频繁打断。根因是展开运算符要先把两个数组完整拷贝到一块新内存20 万加 20 万条数据意味着一次性产生一个 40 万长度的新数组再去构造 Set。这中间产生了至少两份临时大对象。改成逐步 add 之后内存峰值明显下降const set new Set(a); for (let i 0; i b.length; i) { set.add(b[i]); } const result Array.from(set).sort((x, y) x - y);这个案例非常典型功能上完全正确数据规模一放大就暴露常数复杂度问题。我的经验是凡是明确知道数据量可能过万的业务就别为了“一行代码好看”牺牲稳定性拆成两步、三步写更靠谱。最后说点个人体会。像“合并两个无序数组、去重、有序返回”这种题我刷了很多年也帮人 review 了大量代码最大的感受是简单题最能暴露基本功。能否第一时间识别出“无序”这个关键约束知不知道 sort 的默认排序规则会不会处理空数组边界愿不愿意为大数据量做一点防御性设计——这几件事加在一起基本就能判断一个人的代码成熟度。如果你正在准备面试别因为题简单就跳过花一个下午把 JS、Python、Java 三种写法各过一遍顺手练一下链表版本比扫十道重复的 medium 题更值。毕竟真实业务里八成数组操作拆到底层都是合并、去重、排序这三个动作的排列组合。