从相邻元素对还原数组

标签: 数组 哈希表

难度: Medium

存在一个由 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 。如果存在多种解答，返回 其中任意一个 即可。

 

示例 1：

输入：adjacentPairs = [[2,1],[3,4],[3,2]]
输出：[1,2,3,4]
解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。

示例 2：

输入：adjacentPairs = [[4,-2],[1,4],[-3,1]]
输出：[-2,4,1,-3]
解释：数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。

示例 3：

输入：adjacentPairs = [[100000,-100000]]
输出：[100000,-100000]

 

提示：

  • nums.length == n
  • adjacentPairs.length == n - 1
  • adjacentPairs[i].length == 2
  • 2 <= n <= 105
  • -105 <= nums[i], ui, vi <= 105
  • 题目数据保证存在一些以 adjacentPairs 作为元素对的数组 nums

Submission

运行时间: 161 ms

内存: 55.3 MB

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        from collections import defaultdict
        num_cnt = defaultdict(list)
        for adj in adjacentPairs:
            num_cnt[adj[0]].append(adj[1])
            num_cnt[adj[1]].append(adj[0])
        new_num = []
        for kk, vvs in num_cnt.items():
            if len(vvs) == 1:
                new_num.append(kk)
                new_num.append(vvs[0])
                break
        hist = new_num[0]
        start = new_num[1]
        while True:
            if len(num_cnt[start]) == 1:
                break
            cur = num_cnt[start][0]
            if cur == hist:
                cur = num_cnt[start][1]
            new_num.append(cur)
            hist = start 
            start = cur
            
        return new_num

Explain

这个题解首先利用一个哈希表（使用defaultdict(list)）来存储每个数及其相邻的数。键是数组中的数，值是与这个键相邻的数的列表。通过遍历adjacentPairs，将每对相邻的数相互添加到对方的列表中。接着，找到那个只有一个相邻数的数，这个数必定是原数组的端点（起点或终点）。从这个端点开始，逐步构建原数组，直到到达另一个端点。为了确保不重复访问，我们维护一个历史变量来记录上一个访问的元素，以此来决定下一个应该访问的元素。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        from collections import defaultdict
        num_cnt = defaultdict(list)
        # 构建每个数字与其相邻数字的映射
        for adj in adjacentPairs:
            num_cnt[adj[0]].append(adj[1])
            num_cnt[adj[1]].append(adj[0])
        new_num = []
        # 寻找原数组的一个端点
        for kk, vvs in num_cnt.items():
            if len(vvs) == 1:
                new_num.append(kk)
                new_num.append(vvs[0])
                break
        # 从端点开始构建原数组
        hist = new_num[0]
        start = new_num[1]
        while True:
            if len(num_cnt[start]) == 1:
                break
            cur = num_cnt[start][0]
            if cur == hist:
                cur = num_cnt[start][1]
            new_num.append(cur)
            hist = start
            start = cur
        
        return new_num

Explore

在构建哈希表时，每对相邻的数相互添加是为了确保无论从哪一个数开始遍历，都能够访问到与之相邻的另一个数。这种双向连接的方式使得无论遍历的方向如何，都能够依靠已有的连接找到下一个元素。如果只将相邻数添加一次，将无法保证能从任一端点正确遍历整个数组。

题解中通过检查每个元素的邻居数量来确定端点。数组中的端点元素在哈希表中的映射只会有一个邻居，因为端点除了连接到数组内部的元素外，没有其他邻接元素。通过遍历哈希表并检查每个键所对应的值的列表长度，当长度为1时，该键对应的元素就是端点。这种方法确保了只选择了端点元素开始构建数组。

题解中通过维护一个'历史变量'来记录上一个访问过的元素来避免回访。在从端点开始构建数组时，每次将当前元素加入到数组中后，更新历史变量为当前元素，然后根据当前元素的邻居确定下一个元素。如果邻居中有历史变量表示的元素，就选择另一个邻居作为下一个元素。这样通过历史记录确保了不会回访已经加入数组的元素。

在数组构建过程中，`if len(num_cnt[start]) == 1` 的检查是用来确认是否到达了数组的另一个端点。因为在数组中，只有两个端点的元素在哈希表中的邻居列表长度为1。当通过端点开始构建数组，不断更新访问的元素时，如果访问到的新元素的邻居数为1，这表明除了从来的路径外，没有其他的连接路径，因此这个元素必然是数组的另一个端点。