DFS應用題 重建陣列 Restore the Array From Adj Pairs_Leetcode #1743

這題的題目在這裡: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 == n
• adjacentPairs.length == n - 1
• adjacentPairs[i].length == 2
• 2 <= n <= 10^5
• -10^5 <= nums[i], ui, vi <= 10^5
• There exists some nums that has adjacentPairs as 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