从相邻元素对还原数组

无标签

发布日期: 2021-07-25

从相邻元素对还原数组

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

示例

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

数据范围

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui, vi <= 105

提示

除首尾元素，每个元素均出现两次

AC代码一

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& ad) {
        int front,last;
        unordered_map<int,vector<int>> hash;
        for(auto&a:ad){
            hash[a[0]].push_back(a[1]);
            hash[a[1]].push_back(a[0]);
        }
        vector<int> ans;
        for(auto &h:hash){
            if(h.second.size() == 1){
                front = h.first;
                ans.push_back(front);
                last = h.second[0];
                ans.push_back(last);
                break;
            }
        }
        while(hash[last].size() != 1){
            for(int i:hash[last]){
                if(i != front){
                    front = last;
                    last = i;
                    ans.push_back(i);
                    break;
                }
            }
        }
        return ans;
    }
};

思路：
将每个元素与其相邻的元素一对一或一对多的关系，记录在map
中，找到首元素或尾元素，根据映射关系，逐步向后，直至找到尾元素或首元素。如：1->2,2->3,3->4.

AC代码二

    class Solution {
    public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int, vector<int>> mp;
        for (auto& adjacentPair : adjacentPairs) {
            mp[adjacentPair[0]].push_back(adjacentPair[1]);
            mp[adjacentPair[1]].push_back(adjacentPair[0]);
        }

        int n = adjacentPairs.size() + 1;
        vector<int> ret(n);
        for (auto& [e, adj] : mp) {
            if (adj.size() == 1) {
                ret[0] = e;
                break;
            }
        }

        ret[1] = mp[ret[0]][0];
        for (int i = 2; i < n; i++) {
            auto& adj = mp[ret[i - 1]];
            ret[i] = ret[i - 2] == adj[0] ? adj[1] : adj[0];
        }
        return ret;
    }
};