Python程序：从相邻对还原数组

假设我们有一个大小为n-1的二维数组adPair，其中每个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)，执行：
    • 将b插入my_map[a]的末尾
    • 将a插入my_map[b]的末尾
  • 对于my_map中的每个键a和值列表l，执行：
    • 如果l的大小等于1，则
      • nums := 一个包含两个元素(a, l[0])的列表
      • 退出循环
  • 对于范围从1到adPair大小-1的i，执行：
    • a, b := my_map[nums的最后一个元素]
    • 如果a与nums的倒数第二个元素相同，则
      • 将b插入nums的末尾
    • 否则，
      • 将a插入nums的末尾
  • 返回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))

输入

[[3,2],[4,5],[4,3]]

输出

[2, 3, 4, 5]

更新于：2021年10月7日

197 次浏览

开启你的职业生涯

完成课程后获得认证

开始
广告