Chương trình tìm danh sách con ngắn nhất cần sắp xếp để toàn bộ danh sách được sắp xếp trong Python

Cho danh sách nums, tìm độ dài danh sách con ngắn nhất mà nếu sắp xếp nó thì toàn bộ nums sẽ được sắp xếp tăng dần.

Ví dụ, nums = [1,2,5,4,9,10], đầu ra 2 (sắp xếp danh sách con [5,4] -> [4,5] thì toàn bộ sắp xếp).

Các bước giải quyết:

• f := -1, l := -1.
• lst := sorted(nums).
• Duyệt i từ 0 đến độ dài:
  • Nếu nums[i] != lst[i]:
    • Nếu f == -1, f = i.
    • Ngược lại, l = i.
• Nếu l == -1 and f == -1, trả về 0.
• Trả về l - f + 1.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        f = -1
        l = -1
        lst = sorted(nums)
        for i in range(len(nums)):
            if nums[i] != lst[i]:
                if f == -1:
                    f = i
                else:
                    l = i
        if l == -1 and f == -1:
            return 0
        return l - f + 1

ob = Solution()
print(ob.solve([1,2,5,4,9,10]))

Đầu vào

[1,2,5,4,9,10]

Đầu ra

2