Leetcode -1743- Restores an array from adjacent element pairs

[Blog link]

The way to study ๐Ÿ”

The nuggets home page

[Topic description]

There is an integer array, nums, consisting of n different elements, but you can't remember exactly what it is. Good thing you remember every pair of adjacent elements in NUMs. You are given a two-dimensional integer array of adjacentPairs of size n-1, where each adjacentPairs[I] = [UI, vi] indicates that elements UI and vi are adjacent in NUMs. The adjacentPairs are based on the previous pairs of elements nums[I] and nums[I +1] : [nums[I +1] [nums[I +1] [nums[I +1] [nums[I +1] [nums[I]]. These pairs of adjacent elements can appear in any order. Return the original array nums. If multiple solutions exist, return any one of them. Example 1: input: adjacentPairs = [[2,1],[3,4],[3,2] output: [1,2,3,4] explanation: all adjacentPairs of arrays are in adjacentPairs. Note in particular that adjacentPairs[I] only indicate that two elements are adjacent and do not guarantee their left-right order. Example 2: input: adjacentPairs = [[4, 2], [1, 4], [3, 1]] output: [,4,1, 2-3] : there may be a negative number in the array. Another answer, [-3,1,4,-2], would also be taken as the correct answer. Example 3: Input: adjacentPairs = [[100000,-100000]] Output: [100000,-100000]  nums.length == n adjacentPairs.length == n - 1 adjacentPairs[i].length == 2 2 <= n <= 105 -105 <= nums[i], ui, Vi <= 105 The title data guarantees that there are some nums Related Topics array hash tables with adjacentPairs as element pairs ๐Ÿ‘ 41 ๐Ÿ‘Ž 0Copy the code

[Topic link]

Leetcode title link

[making address]

Code link

[ๆ€่ทฏไป‹็ป]

Idea 1: One-way search

  • Go through all the arrays according to the first array, find the second element in order to print

  • How do I validate the first array element

  • We can see that the first element or the last element is only when the number of occurrences is 1

  • Because the output has no ordering of the first and last place we can find the first place in terms of the number of CNTS

  • TLE (39/46)

class Solution { Set<Integer> isValid = new HashSet<>(); public int[] restoreArray(int[][] adjacentPairs) { int[] res = new int[adjacentPairs.length + 1]; HashMap<Integer, Integer> map = new HashMap<>(); for (int[] adp : adjacentPairs ) { map.put(adp[0], map.getOrDefault(adp[0], 0) + 1); map.put(adp[1], map.getOrDefault(adp[1], 0) + 1); } for (int key: map.keyset ()) {if (map.get(key) == 1) {res[0] = key; isValid.add(key); break; }} backTrack(adjacentPairs, res[0], res, 1); return res; } public void backTrack(int[][] adps, int temp, int[] res, int index) { if (index == adps.length + 1) { return; } for (int[] adp : adps) { for (int i = 0; i < 2; i++) { if (adp[i] == temp && ! isValid.contains(adp[1 - i])) { res[index] = adp[1 - i]; isValid.add(adp[1 - i]); backTrack(adps, adp[1 - i], res, index + 1); } } } } }Copy the code


Time complexity O ( n 2 ) Time complexity O(n^2)

Idea 2: Bidirectional scanning

  • No matter which node you start looking for the next node, you will eventually find a final node
  • Turn it over and look for a head node
  • The two lists can be put together
Set<Integer> headSet = new HashSet<>(); public int[] restoreArray(int[][] adjacentPairs) { int[] res = new int[adjacentPairs.length + 1]; List<Integer> goHead = new ArrayList<>(); List<Integer> gotail = new ArrayList<>(); goHead.add(adjacentPairs[0][1]); gotail.add(adjacentPairs[0][0]); gotail.add(adjacentPairs[0][1]); headSet.add(adjacentPairs[0][1]); backTrack(goHead, goHead.get(0), adjacentPairs); backTrack(gotail, gotail.get(1), adjacentPairs); For (int I = 0; i < gotail.size(); i++) { res[i] = gotail.get(gotail.size() - i - 1); } for (int i = gotail.size(), j = 2; j < goHead.size(); i++, j++) { res[i] = goHead.get(j); } return res; } public void backTrack(List<Integer> list, int temp, int[][] ads) { for (int[] ad : ads ) { for (int i = 0; i < 2; i++) { if (ad[i] == temp && ! headSet.contains(ad[1 - i])) { list.add(ad[1 - i]); headSet.add(ad[1 - i]); backTrack(list, ad[1 - i], ads); return; }}}}Copy the code


Time complexity O ( n 2 ) Time complexity O(n^2)

Idea 3: Optimization

  • There’s nothing wrong with either way of thinking
  • It is more likely to be due to writing methods and useless calculations
  • Useless computations are mainly repeated computations in a recursive traversal, and it is perfectly possible not to scan an array that has already been scanned
  • At the same time, adjacent elements of each element can be first scanned by a two-dimensional array
  • Identify the associative array for each element, and then check it directly with get
Set<Integer> headSet = new HashSet<>(); Map<Integer,List<Integer>> map = new HashMap<>(); public int[] restoreArray(int[][] adjacentPairs) { int[] res = new int[adjacentPairs.length + 1]; for (int i = 0; i < adjacentPairs.length; i++) { List<Integer> indexa = map.getOrDefault(adjacentPairs[i][0],new ArrayList<>()); indexa.add(i); map.put(adjacentPairs[i][0],indexa); List<Integer> indexb = map.getOrDefault(adjacentPairs[i][1],new ArrayList<>()); indexb.add(i); map.put(adjacentPairs[i][1],indexb); } List<Integer> goHead = new ArrayList<>(); List<Integer> gotail = new ArrayList<>(); goHead.add(adjacentPairs[0][1]); gotail.add(adjacentPairs[0][0]); gotail.add(adjacentPairs[0][1]); backTrack(goHead, goHead.get(0), adjacentPairs); backTrack(gotail, gotail.get(1), adjacentPairs); For (int I = 0; i < gotail.size(); i++) { res[i] = gotail.get(gotail.size() - i - 1); } for (int i = gotail.size(), j = 2; j < goHead.size(); i++, j++) { res[i] = goHead.get(j); } return res; } public void backTrack(List<Integer> list, int temp, int[][] ads) { for (int i = 0; i< map.get(temp).size(); i++) { for (int j = 0; j < 2; j++) { int index = map.get(temp).get(i); if (ads[index][j] == temp && ! headSet.contains(index)) { list.add(ads[index][1 - j]); headSet.add(index); backTrack(list, ads[index][1 - j], ads); return; }}}}Copy the code

Time complexity O(n)