This article is participating in Python Theme Month. See the link to the event for more details
Topic describes
This is 1743 on LeetCode. Restore array from adjacent element pairs, difficulty is medium.
Tag: “hash table”, “double pointer”, “simulation”
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.Copy the codeExample 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.Copy the codeExample 3:
Input: adjacentPairs = [[100000,-100000]] Output: [100000,-100000]Copy the codeTip:
- nums.length == n
- adjacentPairs.length == n – 1
- adjacentPairs[i].length == 2
- 2 <= n <=
- –
<= nums[i], ui, vi <=
- The title data guarantees that there are arrays with adjacentPairs as elements
Unidirectional construction (hash table count)
Since all adjacences occur in numsnumsnums, suppose one of the valid arrays is ansansans and has length NNN.
Ans [0]ans[0]ans[0] ans[0]ans[0]ans[0] ans[n-1]ans[n−1] ans[n−1] ANS [n−1]ans[n −1]ans[n −1] Ans [n−1] Ans [I]ans[I]ans[I]ans[I]
So we can use a “hash table” to count the numbers that appear in numsnumsnums, find the number that appears once as the first number of ansansans, and then do a “unidirectional construct” based on the given adjacencies, in order to find out which numbers are adjacent to each other. We also need to open a “hash table” to record the adjacencies.
Java code:
class Solution {
public int[] restoreArray(int[][] aps) {
int m = aps.length, n = m + 1;
Map<Integer, Integer> cnts = new HashMap<>();
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] ap : aps) {
int a = ap[0], b = ap[1];
cnts.put(a, cnts.getOrDefault(a, 0) + 1);
cnts.put(b, cnts.getOrDefault(b, 0) + 1);
List<Integer> alist = map.getOrDefault(a, new ArrayList<>());
alist.add(b);
map.put(a, alist);
List<Integer> blist = map.getOrDefault(b, new ArrayList<>());
blist.add(a);
map.put(b, blist);
}
int start = -1;
for (int i : cnts.keySet()) {
if (cnts.get(i) == 1) {
start = i;
break; }}int[] ans = new int[n];
ans[0] = start;
ans[1] = map.get(start).get(0);
for (int i = 2; i < n; i++) {
int x = ans[i - 1];
List<Integer> list = map.get(x);
for (int j : list) {
if(j ! = ans[i -2]) ans[i] = j; }}returnans; }}Copy the codePython 3 code:
class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) - >List[int] :
m = n = len(adjacentPairs)
n += 1
cnts = defaultdict(int)
hashmap = defaultdict(list)
for a, b in adjacentPairs:
cnts[a] += 1
cnts[b] += 1
hashmap[a].append(b)
hashmap[b].append(a)
start = -1
for i, v in cnts.items():
if v == 1:
start = i
break
ans = [0] * n
ans[0] = start
ans[1] = hashmap[start][0]
for i in range(2, n):
x = ans[i - 1]
for j in hashmap[x]:
ifj ! = ans[i -2]:
ans[i] = j
return ans
Copy the code- Time complexity: O(n)O(n)O(n)
- Space complexity: O(n)O(n)O(n)
Bidirectional construction (double pointer)
In solution 1, we use the hash table count to get the original of the first place of ansansans as a starting point for “unidirectional construction”.
Is there a bidirectional construction that uses any number as a starting point?
The answer is obvious. We can construct an array QQQ of length 10610^6106 using ansansans of length 2<=n<=1052 <=n<=10 ^52<=n<=105. Having multiple test cases share a large array).
Here the QQQ array doesn’t have to be 1e61E61E6, as long as our QQQ is larger than twice the size of ansansans, we won’t have a problem crossing the line.
Starting from the middle of the QQQ array, add any one of the elements to the middle, using a “double pointer” to “expand both sides” (l and R point left and right to the insertion position).
When the l pointer and r pointer have NNN values directly, it indicates that the entire Ansansans construction is complete. We can output the values in the range of [L +1,r−1][L +1, r-1][L +1,r−1] as the answer.
Java code:
class Solution {
static int N = (int)1e6+10;
static int[] q = new int[N];
public int[] restoreArray(int[][] aps) {
int m = aps.length, n = m + 1;
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] ap : aps) {
int a = ap[0], b = ap[1];
List<Integer> alist = map.getOrDefault(a, new ArrayList<>());
alist.add(b);
map.put(a, alist);
List<Integer> blist = map.getOrDefault(b, new ArrayList<>());
blist.add(a);
map.put(b, blist);
}
int l = N / 2, r = l + 1;
int std = aps[0] [0];
List<Integer> list = map.get(std);
q[l--] = std;
q[r++] = list.get(0);
if (list.size() > 1) q[l--] = list.get(1);
while ((r - 1) - (l + 1) + 1 < n) {
List<Integer> alist = map.get(q[l + 1]);
int j = l;
for (int i : alist) {
if(i ! = q[l +2]) q[j--] = i;
}
l = j;
List<Integer> blist = map.get(q[r - 1]);
j = r;
for (int i : blist) {
if(i ! = q[r -2]) q[j++] = i;
}
r = j;
}
int[] ans = new int[n];
for (int i = l + 1, idx = 0; idx < n; i++, idx++) {
ans[idx] = q[i];
}
returnans; }}Copy the codePython 3 code:
class Solution:
N = 10支那6 + 10
q = [0] * N
def restoreArray(self, adjacentPairs: List[List[int]]) - >List[int] :
m = len(adjacentPairs)
n = m + 1
hashmap = defaultdict(list)
for a, b in adjacentPairs:
hashmap[a].append(b)
hashmap[b].append(a)
l = self.N // 2
r = l + 1
std = adjacentPairs[0] [0]
lt = hashmap[std]
self.q[l] = std
l -= 1
self.q[r] = lt[0]
r += 1
if len(lt) > 1:
self.q[l] = lt[1]
l -= 1
while (r-1)-(l+1) +1<n:
alt = hashmap[self.q[l+1]]
j = l
for i in alt:
ifi ! = self.q[l+2]:
self.q[j] = i
j -= 1
l = j
blt = hashmap[self.q[r-1]]
j = r
for i in blt:
ifi ! = self.q[r -2]:
self.q[j] = i
j += 1
r = j
ans = [0] * n
for idx in range(n):
ans[idx] = self.q[idx+l+1]
return ans
Copy the code- Time complexity: O(n)O(n)O(n)
- Space complexity: O(n)O(n)O(n)
The last
This is article No.1743 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.