Kiểm tra mảng có thể sắp xếp bằng một lần hoán vị trong Python

Cho mảng số nguyên. Kiểm tra xem có thể sắp xếp mảng theo thứ tự không giảm chỉ bằng một phép hoán vị (swap) hai phần tử hay không.

Ví dụ: [7,8,12,10,11,9] → hoán vị 12 và 9 → mảng sắp xếp → "Can be done".

Giải thuật

• Tạo bản sao mảng và sắp xếp.
• Đếm số vị trí mà mảng gốc khác mảng đã sắp xếp (swap_count).
• Nếu swap_count == 0 (đã sắp xếp) hoặc swap_count == 2 (hoán vị một cặp) → True.

Mã ví dụ

from copy import deepcopy

def solve(input_list):
    temp_list = deepcopy(input_list)
    temp_list.sort()
    swap_count = 0
    for i in range(len(input_list)):
        if input_list[i] != temp_list[i]:
            swap_count += 1
    if swap_count == 0 or swap_count == 2:
        print("Can be done")
    else:
        print("Can't be done")

input_list = [7, 8, 12, 10, 11, 9]
solve(input_list)

Đầu vào

[7, 8, 12, 10, 11, 9]

Đầu ra

Can be done