Chương trình khôi phục mảng từ các cặp liền kề trong Python

Giả sử chúng ta có một mảng 2D được gọi là adPair có kích thước n-1 trong đó mỗi adPair [i] có hai phần tử [ui, vi] biểu thị rằng các phần tử ui và vi nằm kề nhau trong một mảng được gọi là nums, trong nums có n phần tử duy nhất. Chúng ta phải tìm số mảng. Nếu có nhiều giải pháp, hãy trả lại bất kỳ giải pháp nào trong số chúng.

Vì vậy, nếu đầu vào giống như adPair =[[3,2], [4,5], [4,3]], thì đầu ra sẽ là [2,3,4,5]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• my_map:=một bản đồ trống để lưu trữ danh sách các khóa khác nhau
• đối với mỗi cặp (a, b) trong adPair, thực hiện
  • chèn b vào cuối my_map [a]
  • chèn một vào cuối my_map [b]
• đối với mỗi khóa a và danh sách giá trị l trong my_map, hãy thực hiện
  • nếu kích thước của l bằng 1, thì
    • nums:=một danh sách có hai phần tử (a, l [0])
    • ra khỏi vòng lặp
• đối với tôi trong phạm vi từ 1 đến kích thước của adPair - 1, hãy thực hiện
  • a, b:=my_map [phần tử cuối cùng của nums]
  • nếu a giống với phần tử cuối cùng thứ hai của nums, thì
    • chèn b vào cuối nums
  • nếu không,
    • chèn một vào cuối nums
• trả về số

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

[2, 3, 4, 5]