โปรแกรมกู้คืนอาร์เรย์จากคู่ที่อยู่ติดกันใน Python

สมมติว่าเรามีอาร์เรย์ 2 มิติที่เรียกว่า adPair ขนาด n-1 โดยที่ adPair[i] แต่ละรายการมีสององค์ประกอบ [ui, vi] แสดงว่าองค์ประกอบ ui และ vi อยู่ติดกันในอาร์เรย์ที่เรียกว่า nums ใน nums มีองค์ประกอบที่ไม่ซ้ำกัน n รายการ เราต้องหาจำนวนอาร์เรย์ หากมีหลายวิธีแก้ปัญหา ให้ส่งคืนด้วยวิธีใดวิธีหนึ่ง

ดังนั้น หากอินพุตเป็นเหมือน adPair =[[3,2],[4,5],[4,3]] ผลลัพธ์จะเป็น [2,3,4,5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• my_map :=แผนที่ว่างสำหรับเก็บรายการสำหรับคีย์ต่างๆ
• สำหรับแต่ละคู่ (a, b) ใน adPair ให้ทำ
  • แทรก b ที่ส่วนท้ายของ my_map[a]
  • แทรก a ที่ส่วนท้ายของ my_map[b]
• สำหรับแต่ละคีย์ a และรายการค่า l ใน my_map ให้ทำ
  • ถ้าขนาด l เท่ากับ 1 แล้ว
    • nums :=รายการที่มีสององค์ประกอบ (a, l[0])
    • ออกมาจากลูป
• สำหรับฉันในช่วง 1 ถึงขนาดของ adPair - 1 ทำ
  • a, b :=my_map[องค์ประกอบสุดท้ายของ nums]
  • ถ้า a เหมือนกับองค์ประกอบสุดท้ายที่สองของ 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))

อินพุต

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

ผลลัพธ์

[2, 3, 4, 5]