Tìm độ dài mảng con không sắp xếp nhỏ nhất để sắp xếp toàn bộ mảng trong Python

Cho mảng A[0..n-1] chưa sắp xếp. Tìm mảng con A[s..e] có độ dài nhỏ nhất sao cho nếu sắp xếp mảng con này thì toàn bộ mảng sẽ được sắp xếp.

Ví dụ: [2,6,4,8,10,9,15] → kết quả 5 (mảng con [6,4,8,10,9]).

Giải thuật

Cách đơn giản: sắp xếp bản sao mảng, so sánh với mảng gốc để tìm chỉ số đầu và cuối khác nhau.

• Tạo mảng res = sorted(nums).
• Duyệt qua các chỉ số, lưu các vị trí i mà nums[i] != res[i].
• Nếu không có vị trí nào khác → trả về 0.
• Nếu chỉ có 1 vị trí → trả về 1.
• Ngược lại trả về last - first + 1.

Ví dụ

class Solution:
    def findUnsortedSubarray(self, nums):
        res = sorted(nums)
        r = []
        for i in range(len(res)):
            if nums[i] != res[i]:
                r.append(i)
        if not r:
            return 0
        if len(r) == 1:
            return 1
        return r[-1] - r[0] + 1

ob1 = Solution()
print(ob1.findUnsortedSubarray([2,6,4,8,10,9,15]))

Đầu vào

[2,6,4,8,10,9,15]

Đầu ra

5