โปรแกรมค้นหาจำนวน swap ที่จำเป็นในการจัดเรียงอาร์เรย์ใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และเราต้องหาจำนวน swap ที่จำเป็นในการจัดเรียง nums ตามลำดับ ไม่ว่าจะขึ้นหรือลง

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 5, 6, 3, 4] ผลลัพธ์จะเป็น 2 เนื่องจาก nums เริ่มต้นมี [2, 5, 6, 3, 4] ถ้าเราสลับหมายเลข 6 และ 4 อาร์เรย์จะเป็น [2,5,4,3,6] จากนั้น ถ้าเราสลับตัวเลข 5 และ 3 อาร์เรย์จะเป็น [2,3,4,5,6] ดังนั้นจำเป็นต้องมีการแลกเปลี่ยน 2 ครั้งเพื่อให้อาร์เรย์เรียงลำดับจากน้อยไปมาก

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

• กำหนดฟังก์ชัน swap_count() นี่จะใช้เวลา input_arr
  • pos :=รายการใหม่ที่มี tuples (item_postion, item) สำหรับแต่ละรายการใน input_arr
  • จัดเรียงรายการ pos ตามรายการใน input_arr
  • cnt :=0
  • สำหรับดัชนีในช่วง 0 ถึงขนาดของ input_arr ให้ทำ
    • ในขณะที่ True ทำ
      • ถ้า pos[index, 0] เหมือนกับ index แล้ว
        • ออกจากลูป
      • มิฉะนั้น
        • cnt :=swap_count + 1
        • swap_index :=pos[ดัชนี, 0]
        • สลับค่าของ (pos[index], pos[swap_index])
  • คืนสินค้า
• จากฟังก์ชัน/วิธีการหลัก ให้ทำดังนี้ −
  • ส่งคืนขั้นต่ำของ (swap_count(input_arr) , swap_count(input_arr ในลำดับย้อนกลับ))

ตัวอย่าง

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

def swap_count(input_arr):
   pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
   cnt = 0

   for index in range(len(input_arr)):
      while True:
         if (pos[index][0] == index):
            break
         else:
            cnt += 1
            swap_index = pos[index][0]
            pos[index], pos[swap_index] = pos[swap_index], pos[index]

   return cnt

def solve(input_arr):
   return min(swap_count(input_arr), swap_count(input_arr[::-1]))

nums = [2, 5, 6, 3, 4]
print(solve(nums))

อินพุต

[2, 5, 6, 3, 4]

ผลลัพธ์

2