Chương trình đếm số lần hoán vị liền kề để biến đổi danh sách trong Python

Cho hai danh sách L1 và L2 cùng độ dài n, chứa các giá trị duy nhất từ 1 đến n. Tìm số lần hoán vị liền kề (adjacent swaps) tối thiểu để biến L1 thành L2.

Ví dụ

L1 = [0, 1, 2, 3], L2 = [2, 0, 1, 3]

Bước 1: hoán vị 1 và 2 → [0, 2, 1, 3]

Bước 2: hoán vị 0 và 2 → [2, 0, 1, 3] = L2

Kết quả: 2.

Thuật toán (Greedy + Index)

1. Khởi tạo ans = 0.
2. Với mỗi phần tử req trong L2 (theo thứ tự):
   • Tìm chỉ số i của req trong L1 hiện tại.
   • Xóa phần tử tại i khỏi L1.
   • ans += i (số lần swap cần để đưa phần tử về đầu).
3. Trả về ans.

Giải thích: Khi xóa phần tử tại vị trí i, nó tương đương với việc swap nó về phía trước i lần.

Triển khai Python

class Solution:
    def solve(self, L1, L2):
        ans = 0
        for req in L2:
            i = L1.index(req)
            L1.pop(i)
            ans += i
        return ans

# Test
ob = Solution()
L1 = [0, 1, 2, 3]
L2 = [2, 0, 1, 3]
print(ob.solve(L1, L2))  # Output: 2

Độ phức tạp

• Thời gian: O(n²) do index() và pop() mỗi lần O(n).
• Không gian: O(1) thêm (sửa đổi L1 tại chỗ).

Có thể tối ưu về O(n log n) dùng Fenwick Tree / BIT để đếm số phần tử đã xóa trước vị trí hiện tại.