Python 根据相邻关系还原数组的两种方式(单向构造和双向构造)

作者:宫水三叶的刷题日记 时间:2023-09-24 17:08:06 

目录
  • 题目描述

    • 示例 1:

    • 示例 2:

    • 示例 3:

  • 单向构造(哈希表计数)

    • 双向构造(双指针)

      • 最后

        题目描述

        这是 LeetCode 上的 1743. 从相邻元素对还原数组 ,难度为 中等。

        Tag : 「哈希表」、「双指针」、「模拟」

        存在一个由 n 个不同元素组成的整数数组 nums ,但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
        给你一个二维整数数组 adjacentPairs ,大小为 n - 1 ,其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
        题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中,存在形式可能是 [nums[i], nums[i+1]] ,也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。

        返回 原始数组 nums 。如果存在多种解答,返回 其中任意一个 即可。

        示例 1:

        输入:adjacentPairs = [[2,1],[3,4],[3,2]]

        输出:[1,2,3,4]

        解释:数组的所有相邻元素对都在 adjacentPairs 中。
        特别要注意的是,adjacentPairs[i] 只表示两个元素相邻,并不保证其 左-右 顺序。

        示例 2:

        输入:adjacentPairs = [[4,-2],[1,4],[-3,1]]

        输出:[-2,4,1,-3]

        解释:数组中可能存在负数。
        另一种解答是 [-3,1,4,-2] ,也会被视作正确答案。

        示例 3:

        输入:adjacentPairs = [[100000,-100000]]

        输出:[100000,-100000]

        提示:

        • nums.length == n

        • adjacentPairs.length == n - 1

        • adjacentPairs[i].length == 2

        • 2 <= n <= 10510^5105

        • -10510^5105 <= nums[i], ui, vi <= 10510^5105

        • 题目数据保证存在一些以 adjacentPairs 作为元素对的数组

        单向构造(哈希表计数)

        根据题意,由于所有的相邻关系都会出现在 numsnumsnums 中,假设其中一个合法数组为 ansansans,长度为 nnn。

        那么显然 ans[0]ans[0]ans[0] 和 ans[n−1]ans[n - 1]ans[n−1] 在 numsnumsnums 中只存在一对相邻关系,而其他 ans[i]ans[i]ans[i] 则存在两对相邻关系。

        因此我们可以使用「哈希表」对 numsnumsnums 中出现的数值进行计数,找到“出现一次”的数值作为 ansansans 数值的首位,然后根据给定的相邻关系进行「单向构造」,为了方便找到某个数其相邻的数是哪些,我们还需要再开一个「哈希表」记录相邻关系。

        Python 根据相邻关系还原数组的两种方式(单向构造和双向构造)

        Java 代码:


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

        Python 3 代码:


        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]:
                       if j != ans[i - 2]:
                           ans[i] = j
               return ans
        • 时间复杂度:O(n)O(n)O(n)

        • 空间复杂度:O(n)O(n)O(n)

        双向构造(双指针)

        在解法一中,我们通过「哈希表」计数得到 ansansans 首位的原始作为起点,进行「单向构造」。
        那么是否存在使用任意数值作为起点进行的双向构造呢?
        答案是显然的,我们可以利用 ansansans 的长度为 2<=n<=1052 <= n <= 10^52<=n<=105,构造一个长度 10610^6106 的数组 qqq(这里可以使用 static 进行加速,让多个测试用例共享一个大数组)。

        这里 qqq 数组不一定要开成 1e61e61e6 大小,只要我们 qqq 大小大于 ansansans 的两倍,就不会存在越界问题。

        从 qqq 数组的 中间位置 开始,先随便将其中一个元素添加到中间位置,使用「双指针」分别往「两边拓展」(l 和 r 分别指向左右待插入的位置)。

        当 l 指针和 r 指针直接已经有 nnn 个数值,说明整个 ansansans 构造完成,我们将 [l+1,r−1][l + 1, r - 1][l+1,r−1] 范围内的数值输出作为答案即可。

        Python 根据相邻关系还原数组的两种方式(单向构造和双向构造)

        Java 代码:


        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;
           }
        }

        Python 3 代码:


        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:
                       if i != self.q[l+2]:
                           self.q[j] = i
                           j -= 1
                   l = j

        blt = hashmap[self.q[r-1]]
                   j = r
                   for i in blt:
                       if i != 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

        时间复杂度:O(n)O(n)O(n)
        空间复杂度:O(n)O(n)O(n)

        最后

        来源:https://juejin.cn/post/6988676087307829255

        标签:Python,相邻关系,还原数组
        0
        投稿

        猜你喜欢

      • 基于JavaScript 实现拖放功能

        2024-04-22 22:29:20
      • Python使用chardet判断字符编码

        2021-05-14 03:03:52
      • python实现八大排序算法(2)

        2023-09-05 06:28:23
      • 使用pyinstaller打包django的方法实现

        2021-04-10 21:58:11
      • MySQL定位并优化慢查询sql的详细实例

        2024-01-25 20:32:16
      • Python爬虫模拟登录带验证码网站

        2022-02-18 21:33:48
      • python中pymysql的executemany使用方式

        2024-01-12 14:35:46
      • Python获取网页上图片下载地址的方法

        2021-01-22 13:15:26
      • numpy数组的重塑和转置实现

        2022-11-10 10:43:18
      • Vue全局事件总线你了解吗

        2024-04-28 09:25:11
      • python抽取指定url页面的title方法

        2022-11-15 21:52:40
      • MySQL无法启动1067错误的又一种解决方法(机房断电)

        2024-01-13 08:55:25
      • Python OpenCV实现鼠标画框效果

        2022-03-02 10:45:15
      • js读写COOKIE实现记住帐号或密码的代码(js读写COOKIE)

        2024-04-18 10:11:12
      • Goland使用Go Modules创建/管理项目的操作

        2024-04-30 10:03:02
      • oracle命令行删除与创建用户的代码

        2009-03-02 10:54:00
      • 基于Python实现新年倒计时

        2022-02-14 08:41:59
      • Go语言实现一个Http Server框架(一) http库的使用

        2024-02-19 23:25:34
      • 一些文档中没有介绍的SQL Server DBCC命令

        2008-12-09 14:24:00
      • 关于爬虫和反爬虫的简略方案分享

        2022-08-01 09:54:53
      • asp之家 网络编程 m.aspxhome.com