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

链接：1743.从相邻元素对还原数组
难度：Medium
标签：数组、哈希表
简介：存在一个由 n 个不同元素组成的整数数组 nums ，返回 原始数组 nums 。

题解 1 - typescript

• 编辑时间：2021-07-25
• 执行用时：332ms
• 内存消耗：88.3MB
• 编程语言：typescript
• 解法介绍：map 储存一个数两边的值。

function restoreArray(adjacentPairs: number[][]): number[] {
  const map = new Map<number, number[]>();
  for (const [n1, n2] of adjacentPairs) {
    let l1 = map.get(n1);
    if (!l1) map.set(n1, (l1 = []));
    let l2 = map.get(n2);
    if (!l2) map.set(n2, (l2 = []));
    l1.push(n2);
    l2.push(n1);
  }
  const ans: number[] = [];
  for (const [n, l] of map.entries())
    if (l.length === 1) {
      ans.push(n);
      break;
    }
  ans.push(map.get(ans[ans.length - 1])![0]);
  while (map.get(ans[ans.length - 1])!.length !== 1) {
    const last = ans[ans.length - 1];
    const list = map.get(last)!;
    const prev = ans[ans.length - 2];
    const next = list[0] === prev ? list[1] : list[0];
    ans.push(next);
  }
  return ans;
}