blob: 6cf6b63761d912b014e98c3ed8f583fc4f64f1dd (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
# 1743. Restore the Array From Adjacent Pairs
"""
there is an integer array 'nums' that contains 'n' unique elements, but you
have forgotten it. however, you do remember that every pair of adjacent
elements in 'nums'. you are given a 2d integer array 'adjacent_pairs' of size
'n - 1' where each adjacent_pairs[i] = [ui, vi] indicates that the elements
'ui' and 'vi' are adjacent in 'nums'. it is guaranteed that every adjacent
pair of elements 'nums[i]' and 'nums[i + 1]' will exist in 'adjacent_pairs'
either as '[nums[i], nums[i + 1]]'. the pairs can appear in any order. return
the original array 'nums'. if there are multiple solutions, return any of
them.
"""
class Solution(object):
def restoreArray(self, vals):
pairs = defaultdict(list)
for val in vals:
pairs[val[0]].append(val[1])
pairs[val[1]].append(val[0])
ans = []
start = -1000000
for entry in pairs:
if len(pairs[entry]) == 1:
start = entry
break
left = -1000000
ans.append(start)
for i in range(1, len(vals) + 1):
val = pairs[start]
newval = val[0] if val[0] != left else val[1]
ans.append(newval)
left = start
start = newval
return ans
|