Mảng Con Liên Tục Không Sắp Xếp Ngắn Nhất trong Python

Cho một mảng số nguyên, cần tìm một mảng con liên tục sao cho nếu chỉ sắp xếp mảng con đó theo thứ tự tăng dần thì toàn bộ mảng cũng sẽ được sắp xếp. Yêu cầu tìm mảng con ngắn nhất thỏa mãn và trả về độ dài của nó. Ví dụ, với mảng [2,6,4,8,10,9,15], đầu ra là 5 (mảng con là [6,4,8,10,9]).

Thuật toán giải quyết

1. Tạo mảng res là bản sao đã sắp xếp của mảng gốc nums.
2. Khởi tạo danh sách r để lưu các chỉ số nơi hai mảng khác nhau.
3. Duyệt qua từng chỉ số i:
   • Nếu nums[i] != res[i], thêm i vào danh sách r.
4. Nếu r rỗng, trả về 0 (mảng đã sắp xếp). Nếu r chỉ có 1 phần tử, trả về 1.
5. Trả về r[-1] - r[0] + 1 (độ dài mảng con từ chỉ số khác nhau đầu tiên đến cuối cùng).

Ví dụ (Python)

class Solution(object):
    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