C++刷LeetCode（1743. 从相邻元素对还原数组）【图】【邻接表】【规律】
题目描述：存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs = 表示元素 ui 和 vi 在 nums 中相邻。
题目数据保证所有由元素 nums 和 nums 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 , nums] ，也可能是 , nums] 。这些相邻元素对可以 按任意顺序 出现。
返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。
示例 1：
输入：adjacentPairs = [,,]
输出：
解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs 只表示两个元素相邻，并不保证其 左-右 顺序。
示例 2：
输入：adjacentPairs = [,,[-3,1]]
输出：[-2,4,1,-3]
解释：数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。
示例 3：
输入：adjacentPairs = []
输出：
提示：
nums.length == n
adjacentPairs.length == n - 1
adjacentPairs.length == 2
2 <= n <= 105
-105 <= nums, ui, vi <= 105
题目数据保证存在一些以 adjacentPairs 作为元素对的数组 nums
通过次数15,317提交次数22,464
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
int len = adjacentPairs.size() + 1;
vector<int>res(len, INT_MIN);
//用map构建一个邻接表
unordered_map<int, vector<int> >store;
for(int i = 0; i < len-1; i++){
store].push_back(adjacentPairs);
store].push_back(adjacentPairs);
}
//以邻接表中度为1的任何一个数为起点
int pos = 0;
int key = INT_MIN;
for(auto iter = store.begin(); iter != store.end(); iter++){
if((iter -> second).size() == 1){
res = iter -> first;
res = (iter -> second);
key = (iter -> second);
break;
}
}
//继续填充下去
while(pos < len){
if(store.size() == 1){
int temp =store;
if(temp != res){//注意此处的规律！！！
res = temp;
key = temp;
}else{
return res;
}
}else{
for(int i = 0; i < 2; i++){
int temp1 = store;
if(temp1 != res){//注意此处的规律！！！
res = temp1;
key = temp1;
break;
}
}
}
}
return res;
}
};
页:
[1]