Computer Science Asked by James Flanagin on October 21, 2021
Given an array composed of pairs, like this:
[[3,5],[1,5],[3,2],[1,4]]
Each element in the array (call it pair) means that pair[0] and pair[1] are adjacent in the original array. Note, they can come in either order. For instance, for the sample array above, the original array would be:
4,1,5,3,2 (or the reversed version of this)
How can I do this quickly? I tried doing this as follows, which works, but it’s too slow:
Create a hashmap that maps adjacent elements. Map = {3: [5,2], 1: [5,4], 5: [1,3], 4: [1], 2:[3]}. My algorithm would then start with one of the keys that only has a corresponding value length of 1 (in this case either 4 or 2), and then add to an output array, and go through the hashmap. I.e. First I would add 4 to my output, and then go from key of 4 (with a corresponding value of 1), to the key of 1, with corresponding values of 5 and 4. I’d ignore 4 (since it’s already in output), and add 5, then go to the key of 5, and so on and so forth. This is too slow! Is there a better algorithm?
Use indegree or DFS:
unordered_map<int, int> indegree;
unordered_map<int, bool> visited;
unordered_map<int, vector<int>> mp;
for (auto& vect: adjacentPairs) {
mp[vect[0]].push_back(vect[1]);
mp[vect[1]].push_back(vect[0]);
indegree[vect[0]]++;
indegree[vect[1]]++;
}
int start = 0;
for (auto& in : indegree)
if (in.second == 1) {
start = in.first;
break;
}
}
int n = indegree.size();
vector<int> result;
result.push_back(start);
visited[start] = true;
while (result.size() != n) {
for (auto& val : mp[start]) {
if (!visited[val]) {
result.push_back(val);
visited[val] = true;
start = val;
}
}
}
return result;
Answered by frostcs on October 21, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP