Chương trình tìm số lần hoán vị tối thiểu để sắp xếp dãy số trong Python

Mô tả bài toán

Cho một danh sách các số khác nhau. Tìm số lần hoán vị (swap) tối thiểu để sắp xếp danh sách theo thứ tự tăng dần.

Ví dụ: nums = [3, 1, 7, 5] → đầu ra 2 (hoán vị 3 với 1, sau đó 5 với 7).

Giải thuật

1. Tạo bản sao đã sắp xếp: sort_seq = sorted(nums).
2. Xây dựng ánh xạ table từ giá trị sang chỉ số hiện tại trong nums.
3. Khởi tạo swaps = 0.
4. Duyệt qua chỉ số i từ 0 đến n-1:
   • n = nums[i], s_n = sort_seq[i] (giá trị đúng ở vị trí i).
   • Nếu s_n != n:
     • Tăng swaps.
     • Hoán vị nums[i] và nums[table[s_n]].
     • Cập nhật table cho hai giá trị vừa hoán vị.
5. Trả về swaps.

Ví dụ mã Python

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

Đầu vào

[3, 1, 7, 5]

Đầu ra

2