{"id":8049,"date":"2021-01-30T20:53:18","date_gmt":"2021-01-31T04:53:18","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8049"},"modified":"2021-01-30T20:53:47","modified_gmt":"2021-01-31T04:53:47","slug":"leetcode-1743-restore-the-array-from-adjacent-pairs","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1743-restore-the-array-from-adjacent-pairs\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1743. Restore the Array From Adjacent Pairs"},"content":{"rendered":"\n

There is an integer array nums<\/code> that consists of n<\/code> unique <\/strong>elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums<\/code>.<\/p>\n\n\n\n

You are given a 2D integer array adjacentPairs<\/code> of size n - 1<\/code> where each adjacentPairs[i] = [ui<\/sub>, vi<\/sub>]<\/code> indicates that the elements ui<\/sub><\/code> and vi<\/sub><\/code> are adjacent in nums<\/code>.<\/p>\n\n\n\n

It is guaranteed that every adjacent pair of elements nums[i]<\/code> and nums[i+1]<\/code> will exist in adjacentPairs<\/code>, either as [nums[i], nums[i+1]]<\/code> or [nums[i+1], nums[i]]<\/code>. The pairs can appear in any order<\/strong>.<\/p>\n\n\n\n

Return the original array <\/em>nums<\/code>. If there are multiple solutions, return any of them<\/strong><\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> adjacentPairs = [[2,1],[3,4],[3,2]]\nOutput:<\/strong> [1,2,3,4]\nExplanation:<\/strong> This array has all its adjacent pairs in adjacentPairs.\nNotice that adjacentPairs[i] may not be in left-to-right order.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> adjacentPairs = [[4,-2],[1,4],[-3,1]]\nOutput:<\/strong> [-2,4,1,-3]\nExplanation:<\/strong> There can be negative numbers.\nAnother solution is [-3,1,4,-2], which would also be accepted.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> adjacentPairs = [[100000,-100000]]\nOutput:<\/strong> [100000,-100000]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • nums.length == n<\/code><\/li>
  • adjacentPairs.length == n - 1<\/code><\/li>
  • adjacentPairs[i].length == 2<\/code><\/li>
  • 2 <= n <= 105<\/sup><\/code><\/li>
  • -105<\/sup> <= nums[i], ui<\/sub>, vi<\/sub> <= 105<\/sup><\/code><\/li>
  • There exists some nums<\/code> that has adjacentPairs<\/code> as its pairs.<\/li><\/ul>\n\n\n\n
    Solution: Hashtable <\/strong><\/h2>\n\n\n\n
    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.<\/p>\n\n\n\n
    Time complexity:O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector restoreArray(vector>& adjacentPairs) {\n    const int n = adjacentPairs.size() + 1;\n    unordered_map> g;\n    for (const auto& p : adjacentPairs) {\n      g[p[0]].push_back(p[1]);\n      g[p[1]].push_back(p[0]);\n    }\n    \n    vector ans(n);\n    for (const auto& [u, vs] : g)\n      if (vs.size() == 1) {\n        ans[0] = u;\n        ans[1] = vs[0];\n        break;\n      }\n        \n    for (int i = 2; i < n; ++i) {\n      const auto& vs = g[ans[i - 1]];\n      ans[i] = vs[0] == ans[i - 2] ? vs[1] : vs[0];      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[20,578,82,177],"class_list":["post-8049","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-array","tag-construction","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8049","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8049"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8049\/revisions"}],"predecessor-version":[{"id":8051,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8049\/revisions\/8051"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8049"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8049"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8049"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}