這題的題目在這裡:Restore the Array From Adjacent Pairs
題目敘述
題目會給我們一個ｐａｉｒ陣列，裡面都是原本陣列相鄰元素形成的ｐａｉｒ，順序已經被打散。要求我們從ｐａｉｒ陣列重建出原本的陣列。
答案可能有不只一組，任選一組回傳即可。
測試範例
Example 1:
Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.
Example 2:
Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.
Example 3:
Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]
約束條件
Constraints:
nums.length == nadjacentPairs.length == n - 1adjacentPairs[i].length == 22 <= n <= 10^5-10^5 <= nums[i], ui, vi<= 10^5- There exists some
numsthat hasadjacentPairsas its pairs.
演算法
其實相鄰的ｐａｉｒ就對應到圖論中的兩條指向邊，
一條是ｕ－＞ｖ，另一條是ｖ－＞ｕ。
ｕ，ｖ就對應到ｐａｉｒ裡面的兩個數字。
舉例來說
Given adjacentPairs = [[2,1],[3,4],[3,2]]
Corresponding graph in G
1 <-> 2 <-> 3 <-> 4
［２,1］就代表有一條指向邊１－＞２ 和 另一條指向邊 ２－＞１
［３,４］就代表有一條指向邊3－＞4 和 另一條指向邊 4－＞3
［３,２］就代表有一條指向邊3－＞２ 和 另一條指向邊 ２－＞3
如果，從端點１出發，那麼DFS走完整張圖的結果是１－＞２－＞３－＞４
可以還原出陣列［１，２，３，４］
如果，從端點４出發，那麼DFS走完整張圖的結果是４－＞３－＞２－＞１
可以還原出陣列［４，３，２，１］
兩個都是對的答案，任選其中一組回傳即可。
用ｐａｉｒ重建整個ｇｒａｐｈ，以adjacency list的形式儲存起來。
接著，以端點(只出現一次的數值)為出發點，用DFS走訪整張圖，途中經過的路徑，就是還原後的答案，也就是重建好的原始陣列。
程式碼
class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
graph = defaultdict(list)
# update adjacent list in Graph G
for u, v in adjacentPairs:
graph[u].append(v)
graph[v].append(u)
array = []
# Locate starting node whose occurrence = 1
start = next(x for x in graph if len(graph[x]) == 1)
def dfs(node, prev):
# Restore array element
array.append(node)
# DFS to next neighbor, and never go back
for neighbor in graph[node]:
if neighbor != prev:
dfs(neighbor, node)
return
# ================================
# Launch DFS from starting node
dfs(node=start, prev=None)
return array
複雜度分析
時間複雜度:
O(n) DFS拜訪整張圖 = O(V)+ O(E) = O(n)。
建Graph的時間成本 = 掃描 adjacentPairs 的成本 = O(n)
空間複雜度:
O(n) DFS拜訪整張圖 = O(V) = O(n)。
建Graph的空間成本 = graph 這張表的成本 = O(2n) = O(n)
關鍵知識點
聯想到其實相鄰的ｐａｉｒ就對應到圖論中的兩條指向邊，
一條是ｕ－＞ｖ，另一條是ｖ－＞ｕ。
ｕ，ｖ就對應到ｐａｉｒ裡面的兩個數字。
舉例來說
Given adjacentPairs = [[2,1],[3,4],[3,2]]
Corresponding graph in G
1 <-> 2 <-> 3 <-> 4
［２,1］就代表有一條指向邊１－＞２ 和 另一條指向邊 ２－＞１
［３,４］就代表有一條指向邊3－＞4 和 另一條指向邊 4－＞3
［３,２］就代表有一條指向邊3－＞２ 和 另一條指向邊 ２－＞3
Reference:
[1] Python O(n) by DFS [w/ Demo] - Restore the Array From Adjacent Pairs - LeetCode
