力按钮1743 .从相邻的元素恢复数组(点击查看主题) ) )。
主题说明
虽然存在由n个不同要素组成的整数数组nums，但是不记得具体的内容。 幸运的是，我记得nums的所有相邻元素。
给出二维整数数组adjacentPairs。 大小为n - 1，每个助理系列[ I ]=[ ui，vi]表示元素ui和vi以编号相邻。
主题数据确保了所有由元素nums[i]和nums[i 1]组成的相邻元素对都存在于原子对中，存在形式为[nums[i]、nums[i 1]、[nums[I1]]的这些相邻的元素对可以按任意顺序显示。
返回原始数组nums。 有多个答案时，返回任意一个即可。
示例1 :
输入：辅助对象=[ 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 :
输入：代理支付=[ [ 100000，-100000]]
输出： [100000、-100000]提示：
nums.length==日本航空公司. length==n-1航空公司[ I ].length==22=n=10 ^5- 10 ^5=美国航空公司[ I ]，ui
方法1 :散列表
思路和算法
对于一维数组nums的元素nums[i]，如果它是数组的第一个或最后一个元素，则存在该元素，并且只有一个相邻的元素。 对于数组的中间元素，只有两个元素与该元素相邻。
要查找原始数组中的第一个和最后一个元素，请记录每个元素旁边的元素是什么，然后依次检查每个元素旁边的元素的数量。 因为可以返回满足条件的任意数组，所以指定两个元素中的一个作为原始数组的第一个元素，然后根据相邻元素的信息确定数组的第二个和第三个元素，直到确定了最后一个元素为止。
具体来说，用散列表记录每个元素的相邻元素是什么，然后检查散列表，找到了只有一个相邻元素的元素e1作为原始数组的第一个元素。 在中，唯一与e1相邻的元素e2是原始数组的第二个元素。 此时，如果排除与e2相邻的e1，则可以确认与e2相邻的e3是原数组的第三个要素……由此，可以完全推测原数组。
c
类解决方案{2}
公共：
vectorintrestorearray (vectorvectorintadjacentpairs )。
顺序映射，向量映射；
for (自动增益集对：增益集对) {
广告助手[0] .推送后退(广告助手[1]；
广告助手[1] .推送后退(广告助手[0]；
}
intn=调整对. size () 1；
Vectorintret(n；
for (自动：毫米)
if(adj.size ()==1) {
ret[0]=e；
布莱克；
}
}
ret=MP ret0=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; } };Java
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; } }C#
public class Solution { public int[] RestoreArray(int[][] adjacentPairs) { Dictionary<int, IList<int>> dictionary = new Dictionary<int, IList<int>>(); foreach (int[] adjacentPair in adjacentPairs) { if (!dictionary.ContainsKey(adjacentPair[0])) { dictionary.Add(adjacentPair[0], new List<int>()); } if (!dictionary.ContainsKey(adjacentPair[1])) { dictionary.Add(adjacentPair[1], new List<int>()); } dictionary[adjacentPair[0]].Add(adjacentPair[1]); dictionary[adjacentPair[1]].Add(adjacentPair[0]); } int n = adjacentPairs.Length + 1; int[] ret = new int[n]; foreach (KeyValuePair<int, IList<int>> pair in dictionary) { int e = pair.Key; IList<int> adj = pair.Value; if (adj.Count == 1) { ret[0] = e; break; } } ret[1] = dictionary[ret[0]][0]; for (int i = 2; i < n; i++) { IList<int> adj = dictionary[ret[i - 1]]; ret[i] = ret[i - 2] == adj[0] ? adj[1] : adj[0]; } return ret; } }Golang
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 }C
struct HashTable { int key; int arr[2]; UT_hash_handle hh; }; void push(struct HashTable** hashTable, int x, int y) { struct HashTable* tmp; HASH_FIND_INT(*hashTable, &x, tmp); if (tmp == NULL) { tmp = (struct HashTable*)malloc(sizeof(struct HashTable)); tmp->key = x, tmp->arr[0] = y, tmp->arr[1] = INT_MAX; HASH_ADD_INT(*hashTable, key, tmp); } else { tmp->arr[1] = y; } } struct HashTable* query(struct HashTable** hashTable, int x) { struct HashTable* tmp; HASH_FIND_INT(*hashTable, &x, tmp); return tmp; } int* restoreArray(int** adjacentPairs, int adjacentPairsSize, int* adjacentPairsColSize, int* returnSize) { struct HashTable* hashTable = NULL; for (int i = 0; i < adjacentPairsSize; i++) { push(&hashTable, adjacentPairs[i][0], adjacentPairs[i][1]); push(&hashTable, adjacentPairs[i][1], adjacentPairs[i][0]); } int n = adjacentPairsSize + 1; int* ret = (int*)malloc(sizeof(int) * n); *returnSize = n; struct HashTable *iter, *tmp; HASH_ITER(hh, hashTable, iter, tmp) { if (iter->arr[1] == INT_MAX) { ret[0] = iter->key; } } ret[1] = query(&hashTable, ret[0])->arr[0]; for (int i = 2; i < n; i++) { int* adj = query(&hashTable, ret[i - 1])->arr; ret[i] = ret[i - 2] == adj[0] ? adj[1] : adj[0]; } return ret; }JavaScript
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; };复杂度分析
时间复杂度：O(n)。其中 n 是原数组的长度。我们只需要遍历每一个元素一次。空间复杂度：O(n) 。其中 n 是原数组的长度。主要为哈希表的开销。本文作者：力扣
声明：本文归“力扣”版权所有，如需转载请联系。