ตรวจสอบว่าอาร์เรย์สามารถจัดเรียงโดยใช้การสลับระหว่างดัชนีที่กำหนดใน Python . เท่านั้น

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums ซึ่งมีค่าไม่ซ้ำกันตั้งแต่ช่วง [0, n – 1] อาร์เรย์นี้ไม่ได้เรียงลำดับ เรายังมีอาร์เรย์ของคู่อื่น ๆ ซึ่งแต่ละคู่มีดัชนีที่สามารถสลับองค์ประกอบของอาร์เรย์ได้ เราสลับกันได้หลายครั้ง เราต้องตรวจสอบว่าเราสามารถจัดเรียงอาร์เรย์ตามลำดับโดยใช้ swaps เหล่านี้ได้หรือไม่

ดังนั้น หากอินพุตเป็น nums =[6,1,7,3,0,5,4,2] คู่ =[(0,4),(6,0),(2,7)] ดังนั้น เอาต์พุตจะเป็น True เนื่องจากเราสามารถสลับอาร์เรย์ดัชนี (2,7) จะเป็น [6,1,2,3,0,5,4,7] จากนั้นสลับ (6,0) อาร์เรย์จะเป็น [4, 1,2,3,0,5,6,7] จากนั้นสลับ (0,4) เพื่อรับ [0,1,2,3,4,5,6,7]

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

• N :=ขนาดของ nums, P :=จำนวนคู่ในอาร์เรย์คู่
• v :=รายการที่มีจำนวนรายการย่อย N
• เข้าชมแล้ว :=ชุดใหม่
• สำหรับ i ในช่วง 0 ถึง P ให้ทำ
  • แทรกดัชนีที่สองของคู่[i] ลงใน v[ดัชนีแรกของคู่[i]]
  • แทรกดัชนีแรกของคู่[i] ลงใน v[ดัชนีที่สองของคู่[i]]
• สำหรับผมในช่วง 0 ถึง N ให้ทำ
  • ถ้าไม่มาเยี่ยมแล้ว
    • que :=คิวสองสิ้นสุด
    • arr_first :=รายการใหม่
    • arr_second :=รายการใหม่
    • ทำเครื่องหมายว่าเยี่ยมชมแล้ว
    • ใส่ i ต่อท้าย que
    • ในขณะที่ que ไม่ว่างเปล่า ให้ทำ
      • u :=องค์ประกอบด้านหน้าของ que และลบองค์ประกอบด้านหน้าของ que
      • ใส่ u ต่อท้าย arr_first
      • ใส่ nums[u] ต่อท้าย arr_second
      • สำหรับแต่ละ s ใน v[u] ทำ
        • ถ้าไม่มาเยี่ยมก็
          • ทำเครื่องหมายว่าเข้าชมแล้ว
          • ใส่ s ต่อท้าย que
    • arr_first :=เรียงลำดับรายการ arr_first
    • arr_second :=เรียงลำดับรายการ arr_second
    • ถ้า arr_first ไม่เหมือนกับ arr_second แล้ว
      • คืนค่าเท็จ
• คืนค่า True

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

โค้ดตัวอย่าง

from collections import deque

def solve(nums, pairs):
   N = len(nums)
   P = len(pairs)
   v = [[] for i in range(N)]
   visited = set()
 
   for i in range(P):
      v[pairs[i][0]].append(pairs[i][1])
      v[pairs[i][1]].append(pairs[i][0])
 
   for i in range(N):
      if i not in visited:
         que = deque()
         arr_first = []
         arr_second = []
 
         visited.add(i)
         que.append(i)
 
         while len(que) > 0:
           u = que.popleft()
           arr_first.append(u)
           arr_second.append(nums[u])
 
           for s in v[u]:
               if s not in visited:
                 visited.add(s)
                 que.append(s)
 
         arr_first = sorted(arr_first)
         arr_second = sorted(arr_second)
         
         if arr_first != arr_second:
           return False
   return True
 
nums = [6,1,7,3,0,5,4,2]
pairs = [(0,4),(6,0),(2,7)]
print(solve(nums, pairs))

อินพุต

[6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)]

ผลลัพธ์

True