从相邻元素对还原数组 图解题解

这道题到底在问什么

输入

adjacentPairs = [[2,1],[3,4],[3,2]]

输出

[1,2,3,4] (相邻关系:1-2、2-3、3-4)

输入

adjacentPairs = [[4,-2],[1,4],[-3,1]]

输出

[-3,1,4,-2] (含负数,反过来 [-2,4,1,-3] 也算对)

最优解：一步一步想明白

1. 3记牢三件事:相邻对就是边、度为 1 的是端点、走链时跳过来时的邻居。下面一帧帧套它。
2. 4先把出现过的 5 个数摆成 5 个点:15、40、27、33、58。此刻它们之间一条边都没有,右边的邻接表也是空的。接下来把 adjacentPairs 里的每一对,都连成一条无向边。
3. 5看第 0 对相邻元素 [27, 40],它说明 27 和 40 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。
4. 6连上 27 和 40 这条边。因为是无向的,两边都要记:27 的邻居里加上 40、40 的邻居里加上 27。看右边面板,27 现在的度是 1、40 的度是 1。继续下一对。
5. 7看第 1 对相邻元素 [33, 58],它说明 33 和 58 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。
6. 8连上 33 和 58 这条边。因为是无向的,两边都要记:33 的邻居里加上 58、58 的邻居里加上 33。看右边面板,33 现在的度是 1、58 的度是 1。继续下一对。
7. 9看第 2 对相邻元素 [15, 40],它说明 15 和 40 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。
8. 10连上 15 和 40 这条边。因为是无向的,两边都要记:15 的邻居里加上 40、40 的邻居里加上 15。看右边面板,15 现在的度是 1、40 的度是 2。继续下一对。
9. 11看第 3 对相邻元素 [27, 33],它说明 27 和 33 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。
10. 12连上 27 和 33 这条边。因为是无向的,两边都要记:27 的邻居里加上 33、33 的邻居里加上 27。看右边面板,27 现在的度是 2、33 的度是 2。四条边全连完,图就建好了。
11. 13图建好了,扫一遍每个点的度。度为 2 的 40、27、33 都是被夹在中间的元素,而度为 1 的只有 15 和 58 这两个点,它们各自只有一个邻居,正是这条链的两个端头。
12. 14从哪一端起步都能得到合法答案。参考解统一从较小的那个端点出发,也就是 15。把它标成起点,接下来沿着边一个点一个点往前走,同时把走过的值填进还原数组。
13. 15从起点 15 看起。它是端点,邻居只有 40 一个,方向没有悬念,下一步就走向 40。
14. 16把起点 15 填进还原数组的第 0 位。目前 nums 是 [15]。
15. 17走到 40。它有两个邻居:27 和 15。其中 15 是刚才来的那个,跳过它;另一个 27 就是要去的下一站,把这条边点亮。
16. 18把 40 接到还原数组第 1 位。灰色的问号是还没填的位置,继续往后走。
17. 19走到 27。它有两个邻居:40 和 33。其中 40 是刚才来的那个,跳过它;另一个 33 就是要去的下一站,把这条边点亮。
18. 20把 27 接到还原数组第 2 位。灰色的问号是还没填的位置,继续往后走。
19. 21走到 33。它有两个邻居:58 和 27。其中 27 是刚才来的那个,跳过它;另一个 58 就是要去的下一站,把这条边点亮。
20. 22把 33 接到还原数组第 3 位。灰色的问号是还没填的位置,继续往后走。
21. 23走到 58。它是另一个端点,唯一的邻居 33 正是上一步来的地方,没有新的可走,链到此为止,全部还原完成。
22. 24把 58 接到还原数组第 4 位。它是链尾,数组填满了。
23. 25整条链走完,还原数组是 [15, 40, 27, 33, 58]。你可以核对一下:相邻的 15-40、40-27、27-33、33-58 恰好就是题目给的四对,一个不多一个不少,还原正确。反着写成 [58, 33, 27, 40, 15] 也是合法答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
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)
        start = min(x for x, ns in g.items() if len(ns) == 1)
        ans, prev, cur = [], None, start
        while cur is not None:
            ans.append(cur)
            nxt = None
            for v in g[cur]:
                if v != prev:
                    nxt = v
                    break
            prev, cur = cur, nxt
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int, vector<int>> g;
        for (auto& e : adjacentPairs) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        int start = INT_MAX;
        for (auto& [x, ns] : g) if (ns.size() == 1) start = min(start, x);
        vector<int> ans;
        int prev = INT_MIN, cur = start;
        while (true) {
            ans.push_back(cur);
            int nxt = INT_MIN;
            for (int v : g[cur]) if (v != prev) { nxt = v; break; }
            if (nxt == INT_MIN) break;
            prev = cur;
            cur = nxt;
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int[] e : adjacentPairs) {
            g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
            g.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);
        }
        int start = Integer.MAX_VALUE;
        for (Map.Entry<Integer, List<Integer>> e : g.entrySet()) if (e.getValue().size() == 1) start = Math.min(start, e.getKey());
        int[] ans = new int[g.size()];
        int prev = Integer.MIN_VALUE, cur = start;
        for (int i = 0; i < ans.length; i++) {
            ans[i] = cur;
            int next = Integer.MIN_VALUE;
            for (int v : g.get(cur)) if (v != prev) { next = v; break; }
            prev = cur;
            cur = next;
        }
        return ans;
    }
}

复杂度

面试官可能追问