โปรแกรมหาจำนวนการสลับน้อยที่สุดเพื่อเรียงลำดับลำดับตัวเลขใน Python

สมมติว่ามีรายการตัวเลขที่ไม่ซ้ำกัน ต้องการหาจำนวนการสลับ (swaps) น้อยที่สุดเพื่อเรียงลำดับจากน้อยไปมาก

ตัวอย่าง: nums = [3, 1, 7, 5] ผลลัพธ์คือ 2 สลับ 3 กับ 1 แล้วสลับ 5 กับ 7

ขั้นตอนการแก้ปัญหา

1. สร้าง sort_seq = เรียง nums
2. สร้าง map table เก็บ index ของแต่ละค่าใน nums เดิม
3. swaps = 0
4. วนลูป i จาก 0 ถึง n-1:
   • n = nums[i], s_n = sort_seq[i], s_i = table[s_n]
   • ถ้า s_n != n:
     • swaps += 1
     • สลับค่าใน nums และอัปเดต table
5. คืนค่า swaps

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

class Solution:
    def solve(self, nums):
        sort_seq = sorted(nums)
        table = {}
        for i, n in enumerate(nums):
            table[n] = i
        swaps = 0
        for i in range(len(nums)):
            n = nums[i]
            s_n = sort_seq[i]
            s_i = table[s_n]
            if s_n != n:
                swaps += 1
                nums[s_i] = n
                nums[i] = s_n
                table[n] = s_i
                table[s_n] = i
        return swaps

ob = Solution()
nums = [3, 1, 7, 5]
print(ob.solve(nums))

อินพุต

[3, 1, 7, 5]

เอาต์พุต

2