Kiểm tra mảng gần như đã sắp xếp (phần tử lệch tối đa 1 vị trí) trong Python

Mảng gần như đã sắp xếp (almost sorted) khi mỗi phần tử cách vị trí đúng của nó trong mảng đã sắp xếp tối đa 1 đơn vị.

Ví dụ: [10, 30, 20, 40] → True (chỉ 20 và 30 hoán vị).

Thuật toán

1. Duyệt mảng, nếu nums[i] > nums[i+1] thì hoán đổi và bỏ qua phần tử tiếp theo.
2. Sau khi duyệt, kiểm tra lại mảng có tăng dần hoàn toàn không.

Triển khai

def solve(nums):
    i = 0
    while i < len(nums) - 1:
        if nums[i] > nums[i + 1]:
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
            i += 1
        i += 1
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return False
    return True

nums = [10, 30, 20, 40]
print(solve(nums))  # True

Đầu vào / Đầu ra

Input: [10, 30, 20, 40]
Output: True

Phân tích độ phức tạp: O(n) thời gian, O(1) không gian phụ.