Chương trình kiểm tra số lượng đảo chỗ toàn cục và cục bộ có bằng nhau không trong Python

Mô tả bài toán

Cho danh sách nums các số khác nhau. Đảo chỗ toàn cục (global inversion): cặp i < j mà nums[i] > nums[j]. Đảo chỗ cục bộ (local inversion): cặp i, i+1 mà nums[i] > nums[i+1]. Kiểm tra xem số lượng đảo chỗ toàn cục có bằng số lượng đảo chỗ cục bộ hay không.

Ví dụ: nums = [3,2,4] → True (chỉ có cặp (0,1) là cả toàn cục và cục bộ).

Giải thuật (Kiểm tra điều kiện cần đủ)

1. Nếu tồn tại cặp i, j với j >= i+2 mà nums[i] > nums[j] thì số đảo chỗ toàn cục > cục bộ → trả về False.
2. Duyệt i từ 0 đến l-3, j từ i+2 đến l-1: nếu nums[i] > nums[j] trả về False.
3. Trả về True.

Ví dụ mã Python

class Solution:
    def solve(self, nums):
        l = len(nums)
        for i in range(l - 2):
            for j in range(i + 2, l):
                if nums[i] > nums[j]:
                    return False
        return True

ob = Solution()
nums = [3, 2, 4]
print(ob.solve(nums))

Đầu vào

[3, 2, 4]

Đầu ra

True