Pythonで隣接するペアから配列を復元するプログラム

サイズn-1のadPairという2D配列があり、各adPair [i]に2つの要素[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：=2つの要素（a、l [0]）を含むリスト
    • ループから抜け出す
• 1からadPair-1のサイズまでの範囲のiの場合は
  • a、b：=my_map[numsの最後の要素]
  • aがnumsの最後から2番目の要素と同じである場合、
    • 数字の最後にbを挿入
  • それ以外の場合、
    • 数字の最後にaを挿入
• 数値を返す

例

理解を深めるために、次の実装を見てみましょう-

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]