LeetCode 题解工作台
从相邻元素对还原数组
存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。 给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [u i , v i ] 表示元素 u i 和 v i…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
从度为一的点开始遍历图，可以用 DFS，也可以直接遍历。 时间复杂度 ，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。
返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。
示例 1：
输入：adjacentPairs = [[2,1],[3,4],[3,2]] 输出：[1,2,3,4] 解释：数组的所有相邻元素对都在 adjacentPairs 中。 特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。
示例 2：
输入：adjacentPairs = [[4,-2],[1,4],[-3,1]] 输出：[-2,4,1,-3] 解释：数组中可能存在负数。 另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。
示例 3：
输入：adjacentPairs = [[100000,-100000]] 输出：[100000,-100000]
提示：
nums.length == nadjacentPairs.length == n - 1adjacentPairs[i].length == 22 <= n <= 105-105 <= nums[i], ui, vi <= 105- 题目数据保证存在一些以
adjacentPairs作为元素对的数组nums
解题思路
方法一：哈希表
从度为一的点开始遍历图，可以用 DFS，也可以直接遍历。
时间复杂度 ，空间复杂度 。
class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
g = defaultdict(list)
for a, b in adjacentPairs:
g[a].append(b)
g[b].append(a)
n = len(adjacentPairs) + 1
ans = [0] * n
for i, v in g.items():
if len(v) == 1:
ans[0] = i
ans[1] = v[0]
break
for i in range(2, n):
v = g[ans[i - 1]]
ans[i] = v[0] if v[1] == ans[i - 2] else v[1]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element in adjacentPairs is processed once, and space complexity is O(n) due to the storage required for the hash table and the reconstructed array. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate identifies the first element in adjacentPairs.
- question_mark
Candidate efficiently uses a hash table to reconstruct the array.
- question_mark
Candidate uses DFS or array scanning to correctly traverse the array.
常见陷阱
外企场景- error
Forgetting to check for the first element in adjacentPairs.
- error
Misunderstanding the directionality of pairs or their possible order.
- error
Not efficiently using hash tables for lookups, leading to suboptimal performance.
进阶变体
外企场景- arrow_right_alt
Allow duplicate elements in nums, complicating the process of finding the first element.
- arrow_right_alt
Allow the adjacent pairs to be given in a random order, testing the robustness of the solution.
- arrow_right_alt
Require reconstructing the array in reverse order, adjusting traversal logic.