There is an integer array nums
that consists of n
unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums
.
You are given a 2D integer array adjacentPairs
of size n - 1
where each adjacentPairs[i] = [ui, vi]
indicates that the elements ui
and vi
are adjacent in nums
.
It is guaranteed that every adjacent pair of elements nums[i]
and nums[i+1]
will exist in adjacentPairs
, either as [nums[i], nums[i+1]]
or [nums[i+1], nums[i]]
. The pairs can appear in any order.
Return the original array nums
. If there are multiple solutions, return any of them.
Example 1:
Input: adjacentPairs = [[2,1],[3,4],[3,2]] Output: [1,2,3,4] Explanation: This array has all its adjacent pairs in adjacentPairs. Notice that adjacentPairs[i] may not be in left-to-right order.
Example 2:
Input: adjacentPairs = [[4,-2],[1,4],[-3,1]] Output: [-2,4,1,-3] Explanation: There can be negative numbers. Another solution is [-3,1,4,-2], which would also be accepted.
Example 3:
Input: adjacentPairs = [[100000,-100000]] Output: [100000,-100000]
Constraints:
nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui, vi <= 105
- There exists some
nums
that hasadjacentPairs
as its pairs.
Solution: Hashtable
Reverse thinking! For a given input array, e.g.
[1, 2, 3, 4, 5]
it’s adjacent pairs are [1,2] , [2,3], [3,4], [4,5]
all numbers appeared exactly twice except 1 and 5, since they are on the boundary.
We just need to find the head or tail of the input array, and construct the rest of the array in order.
Time complexity:O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: vector<int> restoreArray(vector<vector<int>>& adjacentPairs) { const int n = adjacentPairs.size() + 1; unordered_map<int, vector<int>> g; for (const auto& p : adjacentPairs) { g[p[0]].push_back(p[1]); g[p[1]].push_back(p[0]); } vector<int> ans(n); for (const auto& [u, vs] : g) if (vs.size() == 1) { ans[0] = u; ans[1] = vs[0]; break; } for (int i = 2; i < n; ++i) { const auto& vs = g[ans[i - 1]]; ans[i] = vs[0] == ans[i - 2] ? vs[1] : vs[0]; } return ans; } }; |