[数据结构与算法]1743. 从相邻元素对还原数组

题目描述

存在一个由 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

思路

首先观察一下，我们会发现，如果把数组看着链表的话，给出来的是链表的链。
如果一个数组的长度是n的话，就有n-1个连接关系，
而且对于数组两头的数字，只有一对连接关系，其他的都是两对。
比如[1,2,3,4]，长度是4，连接关系只有3对，[1,2] 、 [2,3] 、[3,4]
而且对于两头的数字1 和 4 来说，各种只有一对 [1,2] 和 [3,4] 。
但是对于中间的数字2 和 3 来说，就都有两对，2 就有[1,2] 和 [2,3] 、3 就有 [2,3] 和[3,4]
所以，只要从任意一个地方开始，根据题目给出的连接关系向两边扩展，就简单粗暴的解决了。

小技巧

1. 多申请一倍的空间来避免数组越界
2. 使用hash表来加速查找的速度

代码

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        int halfSize = adjacentPairs.size();
        vector<int> ans(halfSize * 2 + 2, 0);
        map<int, vector<int>> pairsAdjacent; 
        // 存储每个数字的邻居，最多两个，最少一个
        for (int i = 0; i < halfSize; i++) {
            int a = adjacentPairs[i][0], b = adjacentPairs[i][1];
            pairsAdjacent[a].push_back(b);
            pairsAdjacent[b].push_back(a);
        }
        int j = halfSize + 1, i = j - 1;
        // 从中间开始扩展
        ans[i] = adjacentPairs[0][0], ans[j] = adjacentPairs[0][1]; 
        while (j - i + 1 < halfSize + 1) {
            vector<int> pair = pairsAdjacent[ans[i]];
            // 只有两头的元素才只有一个邻居
            if (pair.size() == 1) {
                ans[i-1] = pair[0];
            } else {
                ans[i-1] = pair[0] == ans[i + 1] ? pair[1] : pair[0];
                i--;
            }
            pair = pairsAdjacent[ans[j]];
            if (pair.size() == 1) {
                ans[j+1] = pair[0];
            } else {
                ans[j+1] = pair[0] == ans[j - 1] ? pair[1] : pair[0];
                j++;
            }
        }
        return vector<int>(ans.begin() + i, ans.begin() + j + 1); 
    }
}

时间复杂度：O(n)O(n)
空间复杂度：O(n)O(n)