题目描述
这是 leetcode 上的 1743. 从相邻元素对还原数组 ，难度为 中等。
tag : 「哈希表」、「双指针」、「模拟」
存在一个由 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 <= 10510^5105
- -10510^5105 <= nums[i], ui, vi <= 10510^5105
- 题目数据保证存在一些以 adjacentpairs 作为元素对的数组
单向构造（哈希表计数）
根据题意，由于所有的相邻关系都会出现在 numsnumsnums 中，假设其中一个合法数组为 ansansans，长度为 nnn。
那么显然 ans[0]ans[0]ans[0] 和 ans[n−1]ans[n – 1]ans[n−1] 在 numsnumsnums 中只存在一对相邻关系，而其他 ans[i]ans[i]ans[i] 则存在两对相邻关系。
因此我们可以使用「哈希表」对 numsnumsnums 中出现的数值进行计数，找到“出现一次”的数值作为 ansansans 数值的首位，然后根据给定的相邻关系进行「单向构造」，为了方便找到某个数其相邻的数是哪些，我们还需要再开一个「哈希表」记录相邻关系。
java 代码：
python 3 代码：
- 时间复杂度：o(n)o(n)o(n)
- 空间复杂度：o(n)o(n)o(n)
双向构造（双指针）
在解法一中，我们通过「哈希表」计数得到 ansansans 首位的原始作为起点，进行「单向构造」。
那么是否存在使用任意数值作为起点进行的双向构造呢？
答案是显然的，我们可以利用 ansansans 的长度为 2<=n<=1052 <= n <= 10^52<=n<=105，构造一个长度 10610^6106 的数组 qqq（这里可以使用 static 进行加速，让多个测试用例共享一个大数组）。
这里 qqq 数组不一定要开成 1e61e61e6 大小，只要我们 qqq 大小大于 ansansans 的两倍，就不会存在越界问题。
从 qqq 数组的 中间位置 开始，先随便将其中一个元素添加到中间位置，使用「双指针」分别往「两边拓展」（l 和 r 分别指向左右待插入的位置）。
当 l 指针和 r 指针直接已经有 nnn 个数值，说明整个 ansansans 构造完成，我们将 [l+1,r−1][l + 1, r – 1][l+1,r−1] 范围内的数值输出作为答案即可。
java 代码：
python 3 代码：
时间复杂度：o(n)o(n)o(n)
空间复杂度：o(n)o(n)o(n)
最后
到此这篇关于python 根据相邻关系还原数组的两种方式(单向构造和双向构造)的文章就介绍到这了,更多相关python 相邻还原数组内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
