class Solution {
public:
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
}
};
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 。如果存在多种解答，返回 其中任意一个 即可。
示例 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 == nadjacentPairs.length == n - 1adjacentPairs[i].length == 22 <= n <= 105-105 <= nums[i], ui, vi <= 105adjacentPairs 作为元素对的数组 nums原站题解
python3 解法, 执行用时: 340 ms, 内存消耗: 62.6 MB, 提交时间: 2022-11-25 21:35:39
class Solution:
N = 10 ** 6 + 10
q = [0] * N
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
m = len(adjacentPairs)
n = m + 1
hashmap = defaultdict(list)
for a, b in adjacentPairs:
hashmap[a].append(b)
hashmap[b].append(a)
l = self.N // 2
r = l + 1
std = adjacentPairs[0][0]
lt = hashmap[std]
self.q[l] = std
l -= 1
self.q[r] = lt[0]
r += 1
if len(lt) > 1:
self.q[l] = lt[1]
l -= 1
while (r-1)-(l+1)+1<n:
alt = hashmap[self.q[l+1]]
j = l
for i in alt:
if i != self.q[l+2]:
self.q[j] = i
j -= 1
l = j
blt = hashmap[self.q[r-1]]
j = r
for i in blt:
if i != self.q[r - 2]:
self.q[j] = i
j += 1
r = j
ans = [0] * n
for idx in range(n):
ans[idx] = self.q[idx+l+1]
return ans
python3 解法, 执行用时: 336 ms, 内存消耗: 58.9 MB, 提交时间: 2022-11-25 21:33:20
class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
m = n = len(adjacentPairs)
n += 1
cnts = defaultdict(int)
hashmap = defaultdict(list)
for a, b in adjacentPairs:
cnts[a] += 1
cnts[b] += 1
hashmap[a].append(b)
hashmap[b].append(a)
start = -1
for i, v in cnts.items():
if v == 1:
start = i
break
ans = [0] * n
ans[0] = start
ans[1] = hashmap[start][0]
for i in range(2, n):
x = ans[i - 1]
for j in hashmap[x]:
if j != ans[i - 2]:
ans[i] = j
return ans
javascript 解法, 执行用时: 420 ms, 内存消耗: 92.1 MB, 提交时间: 2022-11-25 21:32:54
/**
* @param {number[][]} adjacentPairs
* @return {number[]}
*/
var restoreArray = function(adjacentPairs) {
const map = new Map();
for (const adjacentPair of adjacentPairs) {
map.get(adjacentPair[0]) ? map.get(adjacentPair[0]).push(adjacentPair[1]) : map.set(adjacentPair[0], [adjacentPair[1]]);
map.get(adjacentPair[1]) ? map.get(adjacentPair[1]).push(adjacentPair[0]) : map.set(adjacentPair[1], [adjacentPair[0]]);
}
const n = adjacentPairs.length + 1;
const ret = new Array(n).fill(0);
for (const [e, adj] of map.entries()) {
if (adj.length === 1) {
ret[0] = e;
break;
}
}
ret[1] = map.get(ret[0])[0];
for (let i = 2; i < n; i++) {
const adj = map.get(ret[i - 1]);
ret[i] = ret[i - 2] == adj[0] ? adj[1] : adj[0];
}
return ret;
};
java 解法, 执行用时: 97 ms, 内存消耗: 89.2 MB, 提交时间: 2022-11-25 21:32:37
class Solution {
public int[] restoreArray(int[][] adjacentPairs) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int[] adjacentPair : adjacentPairs) {
map.putIfAbsent(adjacentPair[0], new ArrayList<Integer>());
map.putIfAbsent(adjacentPair[1], new ArrayList<Integer>());
map.get(adjacentPair[0]).add(adjacentPair[1]);
map.get(adjacentPair[1]).add(adjacentPair[0]);
}
int n = adjacentPairs.length + 1;
int[] ret = new int[n];
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
int e = entry.getKey();
List<Integer> adj = entry.getValue();
if (adj.size() == 1) {
ret[0] = e;
break;
}
}
ret[1] = map.get(ret[0]).get(0);
for (int i = 2; i < n; i++) {
List<Integer> adj = map.get(ret[i - 1]);
ret[i] = ret[i - 2] == adj.get(0) ? adj.get(1) : adj.get(0);
}
return ret;
}
}
golang 解法, 执行用时: 164 ms, 内存消耗: 24.9 MB, 提交时间: 2022-11-25 21:32:06
func restoreArray(adjacentPairs [][]int) []int {
n := len(adjacentPairs) + 1
g := make(map[int][]int, n)
for _, p := range adjacentPairs {
v, w := p[0], p[1]
g[v] = append(g[v], w)
g[w] = append(g[w], v)
}
ans := make([]int, n)
for e, adj := range g {
if len(adj) == 1 {
ans[0] = e
break
}
}
ans[1] = g[ans[0]][0]
for i := 2; i < n; i++ {
adj := g[ans[i-1]]
if ans[i-2] == adj[0] {
ans[i] = adj[1]
} else {
ans[i] = adj[0]
}
}
return ans
}