Learn-Algorithms 数列交并集面试题精讲：集合交集、有序数组合并与双序列和差最小化

教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载本文源自本仓库面试题笔记 5.3 数列-交并集.md聚焦面试中高频出现的三类数列问题两个集合的交集、两个有序数列的原地合并、以及通过交换使两个序列和之差最小。读完本文你将掌握哈希表求交集 O(MN) 的时空权衡思路、尾部向头部扫描的双指针原地归并技巧以及两序列和差最小化背后的动态规划背包建模方法并能对照仓库中的 HashTable.c 与 insert_sort.c 源码理解其底层实现。一、题目全景这类题考什么在 5 数组数列问题.md 的开篇笔记作者就总结了数组数列类题目的考察范围数组排序、top-k、子数组、多个数组合并与交集。本文件 5.3 数列-交并集.md 正是其中多个数组合并、交集主题下的三个具体问题如何求两个集合的交集如何把两个有序数列合并原地合并进容量足够的数组 A如何通过交换元素使两个序列的和之差最小。三个问题分别对应三类解题思想散列表空间换时间、双指针 分治归并、动态规划 / 贪心近似。这也是数组数列章节反复强调的解题工具箱见 5 数组数列问题.md 中解决这一类问题时可以从以下几个方面考虑的列表蛮力穷举、散列表空间换时间、分治后归并、堆排序求 top-k、排序后二分、贪心或动态规划。二、问题一如何求两个集合的交集2.1 原文档的提问与思路原文档对第一个问题的记录非常精炼但抓住了核心每个集合里面是否有重复元素 思路一hash复杂度 O(MN)这句话拆开来看其实是两个子问题前提判断两个集合 A、B 中各自是否允许重复元素如果集合在数学意义上不允许重复则可以直接进入哈希去重逻辑如果允许重复更接近数组/多重集则交集语义要明确——是元素去重后的交集还是按出现次数取 min 的交集。面试时先与面试官对齐这个前提是这类题目的第一个得分点。主解法哈希表。遍历长度较小的集合假设为 M全部放入哈希表再遍历另一个集合长度 N逐个查表命中即加入交集结果。时间复杂度 O(MN)空间复杂度 O(M)选择小集合建表可以优化空间。2.2 哈希表底层仓库中的拉链法实现为什么hash能给出 O(1) 的单次查询、从而让整体达到 O(MN)仓库 3 Hash Table/HashTable.c 给出了一个完整的哈希表实现可以印证其原理// 拉链法实现也就是链表的数组也是数组和链表优势的结合 typedef struct HashTable{ Entry **head; // 桶数组每个桶指向一条链表 unsigned int size; // 桶数量 unsigned int usage; // 已使用/已插入元素数 }HashTable;typedef struct Entry { struct Entry *next; Hash hash; // key 对应的 hash 值 Key key; Value value; }Entry;该实现采用拉链法链地址法用size个桶组成数组每个桶头挂一条链表冲突的 key 挂在同一条链表上。查询时先由哈希函数定位桶再沿链表比较 key——在负载因子合理的情况下单次查找期望为 O(1)。这就是空间换时间的依据付出 O(M) 的建表空间换来 O(N) 次的近似 O(1) 查询总代价 O(MN)。基于此求交集的标准代码框架如下以 Java 为例可用HashSet充当哈希表// 求两个集合数组的交集输出去重后的交集元素 public static ListInteger intersect(int[] a, int[] b) { SetInteger set new HashSet(); for (int x : a) { // 遍历第一个集合建表O(M) set.add(x); } ListInteger result new ArrayList(); for (int x : b) { // 遍历第二个集合查表O(N) if (set.contains(x)) { // 查表期望 O(1) result.add(x); } } return result; }优化提示遍历时优先选择长度较小的集合建表空间开销为 O(min(M,N))如果题目还要求按较小出现次数取交集则需要改用Map元素, 次数计数第一遍统计次数、第二遍按min(count_a, count_b)输出——这与 5.4 数列-查找.md 中找重复数先排序后遍历的思路互为补充。2.3 追问变体两个有序数组的交集面试官经常追加一问如果两个数组已经有序如何求交集此时哈希法仍可行但双指针更优两个指针分别指向 A、B 的头部比较当前值——相等则收集并同时后移较小的一方后移。时间复杂度 O(MN)空间 O(1)不需要哈希表。这与下文合并两个有序数列的双指针技巧一脉相承属于同一套思想的正反两用。三、问题二合并两个有序数列3.1 题目描述与示例合并两个有序数列 A 和 B其中 A 有足够的空间也就是把 B 合并进 A 数组。A [4,5,6] B [1,2,7] 合并后 A [1,2,4,5,6,7]这是经典题Merge Sorted Array的面试表述A 的物理容量大于其有效元素个数aSize要把 B 的全部元素合并进 A且合并结果仍然有序空间复杂度要求通常为 O(1)不使用额外数组。3.2 思路一合并后归并排序递归原文档给出的第一个思路是合并 2 个数列变成[4,5,6,1,2,7]归并排序即可递归思路。即先把 B 接到 A 的尾部拼成大数组再对整个数组做归并排序。归并排序是分治divide-and-conquer的典型应用仓库 6 Sort/README.md 中给出了它的框架并点明其本质是二叉树的后序遍历分解 → 解决 → 合并 1. 分解将一个数组分成 n/2 个子数组2 路归并 2. 解决将各个子数组排好序 3. 合并merge 两个有序数组合并操作是 O(n)void sort(int[] nums, int low, int high) { int mid (low high) / 2; sort(nums, low, mid); // 左半排好序 sort(nums, mid 1, high); // 右半排好序 /****** 后序遍历位置 ******/ merge(nums, low, mid, high); // 合并两个排好序的子数组 /************************/ }归并排序的merge操作本身复杂度就是 O(n)而本题 A、B 各自已经有序因此先拼成大数组再整体归并排序其实绕了远路——直接对两个有序段做一次 merge 即可这正是思路二。3.3 思路二尾部向头部扫描原地双指针原文档的思路二是尾部向头部扫描将大的值放在尾部。这是本题的正解也是与从头往尾合并的关键区别因为 A 的有效数据占在数组前部、尾部有空位若从前往后 mergeA 的已有元素会被覆盖从尾部向头部写则大元素先落在数组末尾的空位上永远不会覆盖尚未处理的元素天然实现 O(1) 额外空间。原文档给出的代码框架如下// 尾部向头部扫描将大的值放在尾部 static void mergeSequenceList(int[] a, int aSize , int[] b){ int len_a a.length -1; int index_a aSize -1; int index_b b.length -1; while (index_a 0 index_b 0) { // 2个指针都有值时 if (a[index_a] 0 b[index_b] 0) { if (a[index_a] b[index_b]) { a[len_a--] a[index_a--]; }else{ a[len_a--] b[index_b--]; } } // a 无值b有值把剩下 b 放好 if (index_a 0 index_b 0) { while (index_b 0) { a[len_a--] b[index_b--]; } } // a 有值b 无值把剩下 a 放好 if (index_a 0 index_b 0) { while (index_b 0) { // 原文此分支循环体为空 } } } }3.4 原代码的两个缺陷与修正版这份笔记代码作为思路标记是清晰的但直接运行存在两个缺陷面试现场写出可运行的完整版本才是加分项用a[index_a] 0判断是否有值不严谨当数组中包含负数元素时会误判应直接用指针index_a 0判断元素是否已处理完第三个分支逻辑写错了index_b 0时while (index_b 0)的循环体永远不会执行且外层while (index_a 0 index_b 0)一旦某指针为负就退出剩余的拷贝逻辑必须在循环外补齐。修正后的标准实现以 Java 为例/** * 将有序数组 B 合并进有序数组 AA 容量充足 * param a 目标数组长度 aSize b.length * param aSize A 中有效元素的个数 * param b 待合并的 B 数组 */ static void mergeSequenceList(int[] a, int aSize, int[] b) { int len a.length - 1; // 从 A 物理末尾开始写 int i aSize - 1; // A 有效元素区间的末尾 int j b.length - 1; // B 的末尾 while (i 0 j 0) { // 两指针都有值时取大的放尾部 if (a[i] b[j]) { a[len--] a[i--]; } else { a[len--] b[j--]; } } while (j 0) { // B 有剩余直接拷到前面 a[len--] b[j--]; } // A 有剩余时无需处理a[0..i] 本就在数组最前部位置天然正确 }用原文档的示例验证A [4,5,6,_,_,_] a.length 6aSize 3 B [1,2,7] i2 j26 7 → 末尾写 7j1 i2 j16 2 → 写 6i1 i1 j15 2 → 写 5i0 i0 j14 2 → 写 4i-1 循环退出j1拷入 2、1 结果 A [1,2,4,5,6,7] ✓3.5 仓库源码佐证双路归并的 C 实现本仓库 6 Sort/insert_sort.c 中实现了归并排序的两段式核心其中merge_array函数与本题的merge 两个有序段逻辑完全同构区别只是它借助临时空间// 合并 2 个有序数组分配一个临时空间装 a、b 的结果最后将合并结果拷贝到数组 A void merge_array(int *a, int size_a, int *b, int size_b) { int *tmp malloc((size_a size_b) * sizeof(int)); int i, j, k; i j k 0; while (i size_a j size_b) { tmp[k] (a[i] b[j]) ? b[j] : a[i]; // 每次取较小者 } while (i size_a) { tmp[k] a[i]; } // 左段剩余 while (j size_b) { tmp[k] b[j]; } // 右段剩余 for (int p 0; p k; p) { a[p] tmp[p]; } // 拷回原数组 free(tmp); }对比可见两种写法共享同一套骨架两两比较取较小较大者 → 处理剩余段 → 收尾。区别只在存储策略merge_array用临时数组空间 O(MN)从前往后写适合通用归并排序面试题版的mergeSequenceList利用 A 尾部的空位从后往前写零额外空间。这也印证了 6 Sort/README.md 中的结论两个有序数组的合并操作本身是 O(n) 的归并排序的复杂度 O(nlogn) 完全由递归拆分的 logn 层堆叠而来——当输入已经是两个有序段时一次 merge 就够这是思路二优于思路一的根本原因。面试中建议先答思路一归并排序框架展示分治理解再答思路二尾部扫描展示空间优化意识最后给出完整可运行代码。四、问题三两个序列和之差最小4.1 题目描述有两个序列 a、b大小都为 n序列元素的值任意整数、无序 要求通过交换 a、b 中的元素使 [序列 a 元素的和] 与 [序列 b 元素的和] 之间的差最小。例如var a [100, 99, 98, 1, 2, 3]; var b [1, 2, 3, 4, 5, 40];原文档只给出了题目与示例没有给出解法。这是一个典型的数组划分/负载均衡类面试题下面给出两条由浅入深的思路。4.2 思路一动态规划01 背包——精确解关键观察交换 a、b 中的元素等价于从总共 2n 个数中重新挑选 n 个数放入 a其余 n 个放入 b。两个序列的和之差最小就是要让选出的 n 个数之和尽量接近总和的一半total/2。于是问题转化为经典 01 背包物品全部 2n 个元素容量total / 2限制恰好选 n 件目标所选元素之和尽量接近容量不超过容量。设dp[k][v]表示从前 k 件物品中选取若干件件数恰好为某值、总和恰好为 v 是否可达或用三维滚动写法dp[j][v] 从前若干件中选 j 件凑出总和 v 是否可行。状态转移// 布尔背包dp[j][v] 能否选 j 个元素使总和恰为 v boolean[][] dp new boolean[n 1][total / 2 1]; dp[0][0] true; for (int x : all) { // 遍历 2n 个元素 for (int j n - 1; j 0; j--) { // 件数维度倒序滚动 for (int v total / 2; v x; v--) { if (dp[j][v - x]) dp[j 1][v] true; } } } // 从 total/2 往下找第一个 dp[n][v] true 的位置 v // 最小差 |total - 2*v|复杂度 O(n²·total)其中 total 是元素总和。当 n 较大但元素取值范围有限时还可以用 bitset 压缩布尔数组把状态压成位向量进一步提速。这是本题的精确解法也是 8 Algorithms Analysis/动态规划.md 中背包问题模型的直接应用。4.3 思路二贪心交换——近似解面试现场如果不要求精确解可以先给出直观的贪心近似计算当前sum_a、sum_b记差值diff |sum_a - sum_b|反复寻找一对(a[i], b[j])若交换后两序列和之差变小即满足sum_a sum_b时选满足a[i] - b[j] 0且尽量接近diff/2的一对交换则执行交换直到找不到能缩小差值的一对为止。// 贪心交换不断找一对元素交换以缩小和差直到局部最优 while (true) { int diff sumA - sumB; if (diff 0) break; boolean improved false; int bestI -1, bestJ -1, bestNewDiff Math.abs(diff); for (int i 0; i n; i) { for (int j 0; j n; j) { int newDiff Math.abs(diff - 2 * (a[i] - b[j])); // 交换后差变化 2*(a[i]-b[j]) if (newDiff bestNewDiff) { bestNewDiff newDiff; bestI i; bestJ j; } } } if (bestI -1) break; // 无法继续改善 // 交换 a[bestI] 与 b[bestJ]并更新 sumA、sumB }该思路的时间复杂度最坏为 O(n²·k)k 为交换轮数只能保证局部最优不能保证全局最优作为面试热身答案没问题但应当主动补充要精确解需用背包 DP的进阶结论——先贪心给直觉、再 DP 给精确解是这类开放题的最佳应答节奏。4.4 示例推演对题目给出的例子做一次直观观察a [100, 99, 98, 1, 2, 3] → sumA 303 b [1, 2, 3, 4, 5, 40] → sumB 55sumA远大于sumB显然应该把 a 中的大数98、99、100与 b 中的小数1、2、3、4、5大量交换把两个序列的负荷拉平。这正是交换使和差最小问题的本质把总量均分到两个序列上让每个序列各承担接近 total/2 的和。用 4.2 节的背包模型就是从 12 个元素中选出 6 个、使其和尽量接近(30355)/2 179此时最小差|total - 2v|即答案。五、小结一题一思想三个问题串起来正好覆盖数列类面试题的三条主线问题核心思想复杂度仓库佐证集合交集哈希表空间换时间有序时双指针O(MN) 时间、O(M) 空间HashTable.c 拉链法实现合并两个有序数列尾部向头部扫描、双指针原地归并O(MN) 时间、O(1) 空间insert_sort.c 的merge_array两序列和差最小01 背包动态规划精确/ 贪心交换近似精确解 O(n²·total)8 Algorithms Analysis/动态规划.md面试实战建议先对齐前提集合有无重复、数组是否有序、A 的容量是否已知直接决定解法选择先框架后细节参考 9 Algorithms Job Interview/README.md 中总结的刷题框架遍历、递归、双指针、二分、滑动窗口、排序、DP先套框架再补边界代码要可运行原笔记中的 merge 代码是思路示意其中第三个分支存在空循环缺陷正式回答务必给出修正版并口头验证示例数据主动谈优化从合并 归并排序思路一到尾部扫描原地归并思路二从贪心交换近似到背包 DP精确每一次升级都是在展示复杂度与空间的分析能力这正是面试官希望听到的思考轨迹。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Learn-Algorithms 数列排序类面试题精讲从归并排序到奇偶分离的九道实战解法Learn Algorithms 数列排序类面试题精讲从归并排序到奇偶分离的九道实战解法 导读 本文基于 Learn Algorithms 仓库《9 Algo教程Learn-Algorithms 链表双指针实战双链相交检测、有序链表合并与 K 路归并详解Learn Algorithms 链表双指针实战双链相交检测、有序链表合并与 K 路归并详解 本文聚焦算法面试中最高频的「双链表」类问题如何找出两个单向链表教程高级数据结构操作列表、集合与有序集合高级数据结构操作列表、集合与有序集合 本文深入探讨了Redis中三种高级数据结构列表、集合和有序集合在go redis客户端中的操作与应用。详细介绍了列表后端数据库客户端缓存上一篇gh_mirrors/notes9/notes高级技巧10个让你效率倍增的使用方法下一篇腾讯混元7B开源256K长文本处理能力重塑企业级AI应用创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考