从相邻元素对还原数组

[yankewei]

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yankewei]

对于贪心算法，我一直是不理解的， 感觉贪心没有什么固定的模版，不像并查集或者说hash一样

func restoreArray(adjacentPairs [][]int) []int {
    var ret []int

    // 把每个元素的相邻元素组成一个hashMap， key为元素，value 为元素的相邻元素
    m := map[int][]int{}
    for _, v := range adjacentPairs {
        m[v[0]] = append(m[v[0]], v[1])
    m[v[1]] = append(m[v[1]], v[0])
    }

    // 找到第一个元素，或者最后一个元素
    key := adjacentPairs[0][0]
    for k, v := range m {
        // 因为第一个元素或者最后一个元素，它的相邻元素肯定是一个
    if len(v) == 1 {
        key = k
    }
    }

    // 声明一个hashMap，存储已经遍历过的元素，因为Go没有 Set 这种数据结构，需要自己实现，空的 struct 不会占用额外的空间
    exists := map[int]struct{}{}

    for len(m) > 0 {
    ret = append(ret, key)
    exists[key] = struct{}{}
    between := m[key]
    delete(m, key)
    for _, v:= range between {
        if _, e := exists[v]; !e {
        key = v
        }
    }
    }
    return ret
}