Tìm độ dài tối thiểu Mảng con chưa được sắp xếp, sắp xếp giúp mảng hoàn chỉnh được sắp xếp bằng Python

Giả sử chúng ta có một mảng A [0..n-1] chưa được sắp xếp có kích thước n, chúng ta phải tìm mảng con có độ dài nhỏ nhất A [s..e] sao cho bằng cách sắp xếp mảng con này toàn bộ mảng sẽ được sắp xếp. Vì vậy, nếu mảng giống như [2,6,4,8,10,9,15], thì đầu ra sẽ là 5. Mảng con sẽ là [6,4,8,10,9].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=sắp xếp các số dưới dạng một mảng

• ans:=0

• đặt r làm danh sách liên kết

• cho tôi trong phạm vi từ 0 đến độ dài của res

  • nếu nums [i] không giống với res [i], thì hãy chèn i vào r

• nếu độ dài của r là 0 thì trả về 0, nếu độ dài của r là 1 thì trả về 1

• trả về phần tử cuối cùng của r - phần tử đầu tiên của r + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution(object):
   def findUnsortedSubarray(self, nums):
      res = sorted(nums)
      ans = 0
      r = []
      for i in range(len(res)):
         if nums[i] != res[i]:
            r.append(i)
      if not len(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