[数据结构与算法]解题 | 从相邻元素对还原数组

题目

存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。

给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。

题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以按任意顺序出现。

返回原始数组nums 。如果存在多种解答，返回其中任意一个即可。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs

结果

语言：Python3
执行用时：408 ms
内存消耗：68.8 MB

代码

参考官方的两个提示写了两个版本，第一次尝试用递归的思想，提交后显示Timeout，所以考虑避免递归，采用索引存储的方式来减少耗时。

class Solution:

    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        n = len(adjacentPairs) + 1
        res = []

        # Find the first element of nums - it will only appear once in adjacentPairs.
        temp1 = {}  # Count the number of occurrences.
        temp2 = {}  # Save the index(es) of each element in adjacentPairs.
        for i in range(n-1):
            a, b = adjacentPairs[i]
            temp1[a] = temp1.get(a, 0) + 1
            if temp1[a] > 1: 
                temp2[a].append(i)
            else:
                temp2[a] = [i]
            temp1[b] = temp1.get(b, 0) + 1
            if temp1[b] > 1: 
                temp2[b].append(i)
            else:
                temp2[b] = [i]
        first = min(temp1, key=temp1.get)

        # Perform a depth-first search from the first element.
        res.append(first)
        for _ in range(n-1):
            temp_id = temp2[res[-1]][0]
            a, b = adjacentPairs[temp_id]
            if a == res[-1]:
                res.append(b)
                temp2[b].remove(temp_id)
            else:
                res.append(a)
                temp2[a].remove(temp_id)
        
        return res

备选方案（超时未通过）

class Solution:
    def __init__(self):
        self.res = []

    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        # Find the first element of nums - it will only appear once in adjacentPairs.
        temp = {}
        for a, b in adjacentPairs:
            temp[a] = temp.get(a, 0) + 1
            temp[b] = temp.get(b, 0) + 1
        first = min(temp, key=temp.get)

        # Perform a depth-first search from the first element.
        self.res.append(first)
        self.helper(adjacentPairs)
        return self.res

    def helper(self, adjacentPairs):
        for pair in adjacentPairs:
            if self.res[-1] in pair:
                if pair[0] == self.res[-1]:
                    self.res.append(pair[1])
                else:
                    self.res.append(pair[0])
                if len(adjacentPairs) > 1:
                    adjacentPairs.remove(pair)
                    return self.helper(adjacentPairs)