用 Python 编写程序从相邻对中恢复数组

pythonserver side programmingprogramming更新于 2025/12/9 19:24:17

假设我们有一个名为 adPair 的二维数组，大小为 n-1，其中每个 adPair[i] 有两个元素 [ui, vi] 表示元素 ui 和 vi 在名为 nums 的数组中相邻，nums 中有 n 个唯一元素。我们必须找到数组 nums。如果有多个解决方案，则返回其中任何一个。

因此，如果输入为 adPair = [[3,2],[4,5],[4,3]]，则输出将为 [2,3,4,5]

为了解决这个问题，我们将遵循以下步骤 −

my_map := 一个空映射，用于存储不同键的列表
对于 adPair 中的每一对 (a, b)，执行
- 在 my_map[a] 的末尾插入 b
- 在 my_map[b] 的末尾插入 a
对于 my_map 中的每个键 a 和值列表 l，执行
- 如果 l 的大小与 1 相同，则
  - nums := 一个包含两个元素的列表(a, l[0])
  - 退出循环
对于 i 在 1 到 adPair 的大小 - 1 的范围内，执行
- a, b := my_map[nums 的最后一个元素]
- 如果 a 与 nums 的倒数第二个元素相同，则
  - 在 nums 的末尾插入 b
- 否则，
  - 在 nums 的末尾插入 a
返回 nums

示例

让我们看看下面的实现以便更好地理解 −


from collections import defaultdict
def solve(adPair):
   my_map = defaultdict(list)
   for a, b in adPair:
      my_map[a].append(b)
      my_map[b].append(a)

   for a, l in my_map.items():
      if len(l) == 1:
         nums = [a, l[0]]
         break
   for i in range(1, len(adPair)):
      a, b = my_map[nums[-1]]

      if a == nums[-2]:
         nums.append(b)
      else:
         nums.append(a)

   return nums

adPair = [[3,2],[4,5],[4,3]]
print(solve(adPair))