Medium
题目描述
有一个由 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 == n
- adjacentPairs.length == n - 1
- adjacentPairs[i].length == 2
- 2 <= n <= 10^5
- -10^5 <= nums[i], ui, vi <= 10^5
- 存在一些 nums 使得 adjacentPairs 为其相邻元素对。
解题思路
这道题本质上是将相邻对重构成一个链表（或者说一条链）。我们可以将其建模为一个图问题来解决。
解题思路
构建图结构：将每个相邻对看作图中的一条边，构建邻接表。每个元素最多有2个邻居（除了两端的元素）。
找到起点：在一条链中，两端的元素只有1个邻居，而中间的元素有2个邻居。因此我们可以通过统计每个元素的邻居数量来找到起点（或终点）。
深度优先搜索：从起点开始，使用DFS遍历整条链。为了避免回头，我们需要记录上一个访问的元素，确保不会重复访问。
算法步骤
- 遍历所有相邻对，构建哈希表记录每个元素的所有邻居
- 找到只有一个邻居的元素作为起点（链的一端）
- 从起点开始DFS，每次选择一个未访问过的邻居继续遍历
- 将遍历路径记录为结果数组
时间复杂度为O(n)，空间复杂度为O(n)，其中n为数组长度。
代码实现
class Solution {
public:
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
unordered_map<int, vector<int>> graph;
// 构建邻接表
for (auto& pair : adjacentPairs) {
graph[pair[0]].push_back(pair[1]);
graph[pair[1]].push_back(pair[0]);
}
// 找到起点（只有一个邻居的元素）
int start = 0;
for (auto& [node, neighbors] : graph) {
if (neighbors.size() == 1) {
start = node;
break;
}
}
vector<int> result;
int prev = INT_MAX; // 用于记录上一个访问的节点
function<void(int)> dfs = [&](int curr) {
result.push_back(curr);
for (int next : graph[curr]) {
if (next != prev) {
prev = curr;
dfs(next);
break;
}
}
};
dfs(start);
return result;
}
};
class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
from collections import defaultdict
# 构建邻接表
graph = defaultdict(list)
for u, v in adjacentPairs:
graph[u].append(v)
graph[v].append(u)
# 找到起点（只有一个邻居的元素）
start = None
for node, neighbors in graph.items():
if len(neighbors) == 1:
start = node
break
result = []
prev = None
def dfs(curr):
nonlocal prev
result.append(curr)
for next_node in graph[curr]:
if next_node != prev:
prev = curr
dfs(next_node)
break
dfs(start)
return result
public class Solution {
public int[] RestoreArray(int[][] adjacentPairs) {
var graph = new Dictionary<int, List<int>>();
// 构建邻接表
foreach (var pair in adjacentPairs) {
if (!graph.ContainsKey(pair[0])) {
graph[pair[0]] = new List<int>();
}
if (!graph.ContainsKey(pair[1])) {
graph[pair[1]] = new List<int>();
}
graph[pair[0]].Add(pair[1]);
graph[pair[1]].Add(pair[0]);
}
// 找到起点（只有一个邻居的元素）
int start = 0;
foreach (var kvp in graph) {
if (kvp.Value.Count == 1) {
start = kvp.Key;
break;
}
}
var result = new List<int>();
int prev = int.MaxValue;
void Dfs(int curr) {
result.Add(curr);
foreach (int next in graph[curr]) {
if (next != prev) {
prev = curr;
Dfs(next);
break;
}
}
}
Dfs(start);
return result.ToArray();
}
}
var restoreArray = function(adjacentPairs) {
const graph = new Map();
for (const [u, v] of adjacentPairs) {
if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u).push(v);
graph.get(v).push(u);
}
let start;
for (const [node, neighbors] of graph) {
if (neighbors.length === 1) {
start = node;
break;
}
}
const result = [start];
let prev = null;
let current = start;
while (result.length < adjacentPairs.length + 1) {
const neighbors = graph.get(current);
const next = neighbors[0] === prev ? neighbors[1] : neighbors[0];
result.push(next);
prev = current;
current = next;
}
return result;
};
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 哈希表 + DFS | O(n) | O(n) |
- 时间复杂度：O(n)，需要遍历所有相邻对来构建图，然后进行一次DFS遍历
- 空间复杂度：O(n)，需要哈希表存储邻接表和递归调用栈的空间