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 次瀏覽

開啟你的職業生涯

完成課程後獲得認證

開始
廣告