推 pandix: one用list的話複雜度太差了 remove是O(n) 11/11 09:47
→ JerryChungYC: 所以改成全部append完多一個for去看graph內長度為1 11/11 10:15
→ JerryChungYC: 的 會更好嗎 看其他人寫是這樣 11/11 10:15
推 pandix: 恩恩 或是one用set也可以 11/11 10:23
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/description
: 1743. Restore the Array From Adjacent Pairs
: 有一堆整數儲存在一個陣列包含了 n 個不相同元素，你忘記陣列長什麼樣子了但是
: 你記得所有數字的旁邊有哪些數字，給你一個二維陣列adjacentPairs ，adjacentPairs
: [i] = [ui, vi] 表示兩個數字 ui 和 vi 在陣列裡面相鄰，求出原本的陣列長什麼樣子
: ，如果有多種結果返回任意一種即可。
: 思路：
: 1.陣列的數字相鄰關係我們可以把他看成一個邊，這個問題就變成一個圖形問題，我們先
: 把所有的邊轉換成一個無向圖，因為數字不連續所以要用 Map 保存。
: 2.陣列的第一個元素或最後一個元素只可能和一個數字相鄰，我們要從其中一個位置做
: 遍歷才可以走訪到所有元素找到原本的陣列，我這邊是用一個二維陣列記錄相連邊，
: 如果第二個索引位置為 null 就表示這個點只有一個相鄰數字，他必定是起點或終點
: ，從這個點開始遍歷所有相鄰的未走訪點就可以找到原本的陣列。
: 3.遍歷的時候用一個 prev 記錄上一個點避免往回走，遍歷的過程不斷的把數字
: 填充進 res 裡即可。
# Python solution
class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
graph = {}
one = []
for i in adjacentPairs:
if i[0] not in graph:
graph[i[0]] = i[1]
one.append(i[0])
else:
graph[i[0]] = [graph[i[0]], i[1]]
one.remove(i[0])
if i[1] not in graph:
graph[i[1]] = i[0]
one.append(i[1])
else:
graph[i[1]] = [graph[i[1]], i[0]]
one.remove(i[1])
prev = one[0]
output = []
while one:
output.append(prev)
last = graph[prev]
if isinstance(graph[last], list):
graph[last].remove(prev)
graph[last] = graph[last][0]
prev = last
else:
output.append(last)
break
return output
這個第40個測資會TLE
是因為 多用一個one去找出頭尾的數
還是因為 在while內使用remove的關係(ChatGPT說的)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.86.127 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699666684.A.E09.html