推 oin1104: 大師 我做這題做到一半 吐了 11/10 23:12
https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/description
1743. Restore the Array From Adjacent Pairs
有一堆整數儲存在一個陣列包含了 n 個不相同元素，你忘記陣列長什麼樣子了但是
你記得所有數字的旁邊有哪些數字，給你一個二維陣列adjacentPairs ，adjacentPairs
[i] = [ui, vi] 表示兩個數字 ui 和 vi 在陣列裡面相鄰，求出原本的陣列長什麼樣子
，如果有多種結果返回任意一種即可。
思路：
1.陣列的數字相鄰關係我們可以把他看成一個邊，這個問題就變成一個圖形問題，我們先
把所有的邊轉換成一個無向圖，因為數字不連續所以要用 Map 保存。
2.陣列的第一個元素或最後一個元素只可能和一個數字相鄰，我們要從其中一個位置做
遍歷才可以走訪到所有元素找到原本的陣列，我這邊是用一個二維陣列記錄相連邊，
如果第二個索引位置為 null 就表示這個點只有一個相鄰數字，他必定是起點或終點
，從這個點開始遍歷所有相鄰的未走訪點就可以找到原本的陣列。
3.遍歷的時候用一個 prev 記錄上一個點避免往回走，遍歷的過程不斷的把數字
填充進 res 裡即可。
Java Code：
----------------------------------------------------------------
class Solution {
public int[] restoreArray(int[][] adjacentPairs) {
Map<Integer, Integer[]> map = new HashMap<>();
for (int[] pair : adjacentPairs) {
if (!map.containsKey(pair[0])) {
map.put(pair[0], new Integer[]{pair[1], null});
} else {
map.get(pair[0])[1] = pair[1];
}
if (!map.containsKey(pair[1])) {
map.put(pair[1], new Integer[]{pair[0], null});
} else {
map.get(pair[1])[1] = pair[0];
}
}
int next = 0;
// 找出陣列頭或尾
for (Map.Entry<Integer, Integer[]> entry : map.entrySet()) {
if (entry.getValue()[1] == null) {
next = entry.getKey();
break;
}
}
int[] res = new int[adjacentPairs.length + 1];
res[0] = next;
int prev = Integer.MIN_VALUE;
for (int i = 1; i < res.length; i++) {
Integer[] pair = map.get(next);
if (prev == pair[0]) {
next = pair[1];
} else {
next = pair[0];
}
prev = res[i - 1];
res[i] = next;
}
return res;
}
}
----------------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699628548.A.665.html
※ 編輯: Rushia (122.100.73.13 臺灣), 11/10/2023 23:11:33