一定要早日上岸鸭 · July 25, 2021 0

1743. 从相邻元素对还原数组

1743. 从相邻元素对还原数组

思路:

哈希表存储所有的值和对应的pair;例如 [[2,1],[3,4],[3,2]] 其对应的哈希表应为:

21,3
12
34,2
43

可以看到1,4只有一个旁边的点,其一定为一个是开头一个是结尾

若1为开头,则根据pair 2

然后可以找到2的pair为1,3由于1在其左,所以3一定在2右边 根据key=3得[4,2] 所以4在3右边

代码:

class Solution { public int[] restoreArray(int[][] adjacentPairs) { Map<Integer, List<Integer>> hm = new HashMap<Integer, List<Integer>>(); for(int[] adjacentPair:adjacentPairs){ hm.putIfAbsent(adjacentPair[0], new ArrayList<Integer>()); hm.putIfAbsent(adjacentPair[1], new ArrayList<Integer>()); hm.get(adjacentPair[0]).add(adjacentPair[1]); hm.get(adjacentPair[1]).add(adjacentPair[0]); } int[] ret = new int[adjacentPairs.length+1]; for(Map.Entry<Integer, List<Integer>> entry : hm.entrySet()){ if(entry.getValue().size()==1){ ret[0] = entry.getKey(); break; } } ret[1] = hm.get(ret[0]).get(0); for(int i=2; i<ret.length; i++){ List<Integer> ls = hm.get(ret[i-1]); if(ls.get(0)==ret[i-2]){ ret[i]=ls.get(1); } else{ ret[i] = ls.get(0); } } return ret; } }

法2:https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/solution/gong-shui-san-xie-yi-ti-shuang-jie-dan-x-elpx/

双指针从中间开始一个向左一个向右:

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]; } return ans; } }