教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读本文围绕 LeetCode 第 1743 题「从相邻元素对还原数组」以 LeetCode/1741-1750/1743. 从相邻元素对还原数组中等.md 的完整题解为骨架系统拆解“哈希表计数 单向构造”与“双指针 双向构造”两条解题路线并结合 LogicStack-LeetCode 仓库的题目索引体系说明该题在“哈希表”“双指针”“模拟”三类 Tag 下的定位。读完本文你将掌握如何利用“端点元素相邻关系唯一”的性质定位数组首尾如何用邻接关系哈希表在 O(n) 时间内线性还原数组以及如何借助静态大数组 双指针从任意元素出发双向扩展规避单向构造对“起点”的依赖。题目背景与仓库定位本仓库 README.md 定位为“日更”算法仓库收录公众号「宫水三叶的刷题日记」的“刷穿 LeetCode”系列题解。本题解位于 LeetCode/1741-1750/ 目录是系列第 No.1743 篇。在仓库的 Tag 索引体系中本题同时出现在三份索引文档中Index/哈希表.md哈希表计数与邻接关系记录的核心场景Index/双指针.md双向构造解法中的双指针扩展技巧Index/模拟.md按相邻关系逐位“拼接”数组的模拟过程。在 Index/哈希表.md、Index/双指针.md 与 Index/模拟.md 中本题均被标注为推荐指数 四星与 3. 无重复字符的最长子串、15. 三数之和 等经典哈希表/双指针题目同级说明该题在两类数据结构技巧上都具备较高训练价值。题目描述与关键性质题目信息题号1743难度中等来源LeetCode「从相邻元素对还原数组」Restore the Array From Adjacent PairsTag哈希表、双指针、模拟。题意存在一个由n个不同元素组成的整数数组nums你只记得其中每一对相邻元素。给定二维整数数组adjacentPairs大小为n - 1其中每个adjacentPairs[i] [u_i, v_i]表示元素u_i和v_i在nums中相邻。题目保证所有nums[i]与nums[i1]组成的相邻元素对都存在于adjacentPairs中存在形式可能是[nums[i], nums[i1]]或[nums[i1], nums[i]]且这些相邻元素对可以按任意顺序出现。要求返回原始数组nums若存在多种解答返回任意一个即可。三个示例示例 1adjacentPairs [[2,1],[3,4],[3,2]]输出[1,2,3,4]注意[2,1]只表示 2 与 1 相邻不保证左-右顺序因此反向数组[4,3,2,1]同样是合法答案。示例 2adjacentPairs [[4,-2],[1,4],[-3,1]]输出[-2,4,1,-3]。数组中可能存在负数哈希表需以数值本身为键与正负无关另一合法解答是[-3,1,4,-2]。示例 3adjacentPairs [[100000,-100000]]输出[100000,-100000]覆盖 n 2 的边界情形只有一对相邻关系两个元素互为端点。数据范围与约束约束项取值范围数组长度2 n 10^5相邻对数量adjacentPairs.length n - 1每对长度adjacentPairs[i].length 2数值范围-10^5 nums[i], u_i, v_i 10^5数据保证一定存在以adjacentPairs作为元素对的数组核心性质端点唯一性这是本题最关键的观察在最终数组ans中首元素ans[0]和尾元素ans[n-1]只存在一对相邻关系而其他所有中间元素ans[i]0 i n-1都存在两对相邻关系。由于nums中元素互不相同这一性质可直接用于定位起点对全部数值做出现次数计数出现次数为 1 的数值必然是数组的某一端单向构造确定起点后逐位沿着邻接关系“走到头”即可还原整条链。解法一单向构造哈希表计数算法思路第一步用两个哈希表完成信息收集cnts统计每个数值在相邻关系中出现的次数出现 1 次的是端点出现 2 次的是中间元素map记录每个数值的邻接数值列表。因为元素互不相同且最终数组是一条链每个中间元素恰好有 2 个邻居端点恰好有 1 个邻居。第二步从cnts中取出出现次数为 1 的任意数值作为start它就是数组某一端的元素。第三步单向构造ans[0] startans[1]直接取start的唯一邻居此后对于i 2取x ans[i-1]的邻居列表排除掉刚用过的ans[i-2]剩下的那个邻居就是ans[i]如此循环直到填满长度为n的答案数组。正确性要点“排除前驱”是单向构造的关键中间元素有 2 个邻居其中 1 个是已经确定的前一个元素另一个才是下一个要填的元素由于数据保证存在合法数组且元素互不相同这一“排除法”每次都能唯一确定下一个元素不会出现歧义或死循环时间复杂度和空间复杂度均为O(n)哈希表的插入与查询均为均摊 O(1)总元素数为 2(n-1)线性可过n 10^5的数据范围。Java 实现class Solution { public int[] restoreArray(int[][] adjacentPairs) { int m adjacentPairs.length, n m 1; MapInteger, Integer cnts new HashMap(); MapInteger, ListInteger map new HashMap(); for (int[] ap : adjacentPairs) { int a ap[0], b ap[1]; cnts.put(a, cnts.getOrDefault(a, 0) 1); cnts.put(b, cnts.getOrDefault(b, 0) 1); ListInteger alist map.getOrDefault(a, new ArrayList()); alist.add(b); map.put(a, alist); ListInteger blist map.getOrDefault(b, new ArrayList()); blist.add(a); map.put(b, blist); } int start -1; for (int i : cnts.keySet()) { if (cnts.get(i) 1) { start i; break; } } int[] ans new int[n]; ans[0] start; ans[1] map.get(start).get(0); for (int i 2; i n; i) { int x ans[i - 1]; ListInteger list map.get(x); for (int j : list) { if (j ! ans[i - 2]) ans[i] j; } } return ans; } }C 实现class Solution { public: vectorint restoreArray(vectorvectorint adjacentPairs) { unordered_mapint, int cnts; unordered_mapint, vectorint map; for(auto pair : adjacentPairs){ int a pair[0], b pair[1]; cnts[a], cnts[b]; map[a].push_back(b); map[b].push_back(a); } int start; for(auto i : cnts) { if(i.second 1){ start i.first; break; } } int n adjacentPairs.size() 1; vectorint ans(n); ans[0] start; ans[1] map[start][0]; for(int i 2; i n; i){ int x ans[i - 1]; for(int j : map[x]) if(j ! ans[i-2]) ans[i] j; } return ans; } };Python 实现class Solution: def restoreArray(self, adjacentPairs: List[List[int]]) - List[int]: cnts defaultdict(int) map defaultdict(list) for ap in adjacentPairs: a, b ap[0], ap[1] cnts[a] 1 cnts[b] 1 map[a].append(b) map[b].append(a) start next(i for i in cnts if cnts[i] 1) n len(adjacentPairs) 1 ans [0] * n ans[0] start ans[1] map[start][0] for i in range(2, n): x ans[i - 1] for j in map[x]: if j ! ans[i - 2]: ans[i] j return ansTypeScript 实现function restoreArray(adjacentPairs: number[][]): number[] { const cnts: {[key: number]: number} {}; const map: {[key: number]: number[]} {}; for(let pair of adjacentPairs){ let a: number pair[0], b: number pair[1]; cnts[a] !cnts[a] ? 1 : cnts[a] 1; cnts[b] !cnts[b] ? 1 : cnts[b] 1; if(!map[a]) map[a] []; if(!map[b]) map[b] []; map[a].push(b); map[b].push(a); } let start: number; for(let key in cnts){ if(cnts[key] 1){ start Number(key); break; } } const n: number adjacentPairs.length 1; const ans: number[] Array(n).fill(0); ans[0] start; ans[1] map[start][0]; for(let i 2; in; i){ let x: number ans[i-1]; for(let j of map[x]){ if(j ! ans[i-2]) ans[i] j; } } return ans; };时间复杂度O(n)空间复杂度O(n)解法二双向构造双指针算法动机解法一依赖“先定位端点再单向推进”本质是单向前驱排除法。解法二换一个角度提问是否存在使用任意数值作为起点进行的双向构造答案是肯定的。由于数组本身是一条“链”从链上任意一个节点出发都可以向左右两个方向同时扩展最终覆盖整条链。双向构造的收益在于不需要先统计出现次数来寻找端点省去cnts哈希表起点任意构造过程天然对称左右两半同时进行直观上更“平均”。算法思路利用ans的长度满足2 n 10^5这一条件构造一个长度为10^6的静态数组qJava 中用static修饰让多个测试用例共享这个大数组避免反复分配大块内存。这里q数组不一定要开成1e6大小只要q大小大于ans的两倍就不会存在越界问题。以N 1e6 10、n最大为1e5为例从中间向两侧各扩展n-1个位置左右各需要约1e5空间N/2足够容纳。具体步骤从q数组的中间位置开始l N / 2, r l 1任取一个元素放入中间位置以adjacentPairs[0][0]作为起始元素std将其放入q[l--]左指针位置再将其邻居放入q[r]右指针位置若起始元素有两个邻居多余的邻居放到q[l--]使用双指针分别向两边扩展以q[l1]为当前左端点在其邻居列表中排除q[l2]得到新的左邻居填入q[j--]并更新l对称地以q[r-1]为当前右端点排除q[r-2]后得到新的右邻居填入q[j]并更新r当l指针和r指针之间已有n个数值即(r - 1) - (l 1) 1 n不再成立说明整个ans构造完成将[l 1, r - 1]范围内的数值拷贝输出作为答案。双指针扩展的细节左右扩展的“排除法”与单向构造本质相同当前端点的邻居中除了已经确定的内侧相邻元素q[l2]或q[r-2]剩下的就是外侧新元素两个指针l、r分别表示“下一个待写入位置的左边/右边”每轮扩展后l左移、r右移窗口[l1, r-1]逐步扩大直至覆盖全部n个元素起始元素std若恰好是端点只有 1 个邻居则左右扩展有一侧立即结束若std是中间元素有 2 个邻居初始l、r两侧各有一个邻居扩展从两端对称推进。无论哪种情况都能正确还原整条链。Java 实现class Solution { static int N (int)1e610; static int[] q new int[N]; public int[] restoreArray(int[][] adjacentPairs) { int m adjacentPairs.length, n m 1; MapInteger, ListInteger map new HashMap(); for (int[] ap : adjacentPairs) { int a ap[0], b ap[1]; ListInteger alist map.getOrDefault(a, new ArrayList()); alist.add(b); map.put(a, alist); ListInteger blist map.getOrDefault(b, new ArrayList()); blist.add(a); map.put(b, blist); } int l N / 2, r l 1; int std adjacentPairs[0][0]; ListInteger list map.get(std); q[l--] std; q[r] list.get(0); if (list.size() 1) q[l--] list.get(1); while ((r - 1) - (l 1) 1 n) { ListInteger alist map.get(q[l 1]); int j l; for (int i : alist) { if (i ! q[l 2]) q[j--] i; } l j; ListInteger blist map.get(q[r - 1]); j r; for (int i : blist) { if (i ! q[r - 2]) q[j] i; } r j; } int[] ans new int[n]; for (int i l 1, idx 0; idx n; i, idx) { ans[idx] q[i]; } return ans; } }C 实现#define N 1000010 class Solution { public: vectorint restoreArray(vectorvectorint adjacentPairs) { int m adjacentPairs.size(), n m 1; unordered_mapint, vectorint map; for(auto pair : adjacentPairs){ int a pair[0], b pair[1]; map[a].push_back(b); map[b].push_back(a); } int l N / 2, r l 1; int s adjacentPairs[0][0]; vectorint q(N, 0); q[l--] s; q[r] map[s][0]; if (map[s].size() 1) q[l--] map[s][1]; while ((r - 1) - (l 1) 1 n){ vectorint list map[q[l 1]]; int j l; for(auto i : list){ if(i ! q[l 2]) q[j--] i; } l j; list map[q[r - 1]]; j r; for(auto i : list){ if(i ! q[r - 2]) q[j] i; } r j; } vectorint ans(n); for(int i l 1, idx 0; idx n; i, idx){ ans[idx] q[i]; } return ans; } };时间复杂度O(n)空间复杂度O(n)q为固定大小的静态/预分配数组两个哈希表存储全部邻接关系两解法对比与适用场景维度解法一单向构造哈希表计数解法二双向构造双指针核心数据结构cnts计数表 map邻接表map邻接表 静态大数组q起点选择必须找到出现次数为 1 的端点任意元素取adjacentPairs[0][0]构造方向从端点单向推进从中间向左右双向推进是否依赖“端点唯一性”依赖用于定位 start不依赖起点任意时间 / 空间复杂度O(n) / O(n)O(n) / O(n)代码简洁度更直观逻辑更短指针边界稍复杂需注意窗口判断选型建议追求思路清晰、易于向面试官解释时首选解法一“端点唯一性 → 计数定位 → 排除前驱单向推进”三步逻辑一气呵成想展示对数组与双指针的控制力、并利用静态数组减少重复分配开销时可选解法二其“从任意点向两侧生长”的思路也能迁移到其他链式还原问题如根据相邻关系重建拓扑链、按边重建路径等场景。边界情况与易错点负数值nums[i]可以是负数示例 2哈希表以数值为键即可注意 Python 的defaultdict(int)与 Java 的getOrDefault均天然支持负数键n 2 的极简情形示例 3只有一对相邻关系两端点各出现 1 次map.get(start).get(0)即唯一邻居单向构造一步完成双向构造中std只有 1 个邻居if (list.size() 1)分支不触发左右扩展一侧立即因窗口已满而结束排除前驱的边界单向构造从i 2开始才需要排除ans[i-2]ans[1]直接取起点唯一邻居无需排除逻辑双向构造的越界防护q长度必须大于2 * n否则从中间向两侧扩展时可能越界本题N 1e6 10相对n 1e5留有充分余量答案方向不唯一正向与反向数组均满足相邻关系约束题目允许返回任意一个无需对答案方向做额外判定。系列背景与仓库延伸本题解来自「刷穿 LeetCode」系列文章第No.1743篇。该系列自 2021/01/01 起持续更新目标是优先刷完 LeetCode 上所有不带锁的题目并在每篇题解中给出最简洁的代码与必要的通解模板。本题在仓库中的完整题解位于 LeetCode/1741-1750/1743. 从相邻元素对还原数组中等.md其讲解的“哈希表计数定位端点”思想与同仓库中 137. 只出现一次的数字 II哈希计数、138. 复制带随机指针的链表哈希表映射关系等题目同属哈希表训练专题双指针构造技巧则可在 Index/双指针.md 索引下与其他双指针题目对比学习。若需在本地复现与调试本题可通过git clone https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode获取仓库后参照各语言代码在 LeetCode 对应题号页面提交验证。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode 0246 中心对称数AlgoNote 哈希表 双指针解法深度解析LeetCode 0246 中心对称数AlgoNote 哈希表 双指针解法深度解析 导读 本文围绕「算法通关手册」AlgoNote中 LeetCode教程文档知识库LogicStack-LeetCode 刷题笔记双指针与通用解法吃透数组移除元素问题LeetCode 26 / 27LogicStack LeetCode 刷题笔记双指针与通用解法吃透数组移除元素问题LeetCode 26 / 27 本篇技术指南围绕公众号「宫水三叶的刷教程文档LeetCode 1711 大餐计数哈希表与位运算双剑合璧的「和为 2 的幂」配对计数LogicStack-LeetCode 题解LeetCode 1711 大餐计数哈希表与位运算双剑合璧的「和为 2 的幂」配对计数LogicStack LeetCode 题解 大餐计数Count教程文档上一篇Windows 10完美解决方案轻松实现HEIC缩略图显示下一篇NodeMCU 固件中的 Lua Compact Debug (LCD)用紧凑行号编码与可裁剪调试信息为 ESP8266 省下每字节 RAM创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考