Mảng con liên tục không được sắp xếp ngắn nhất trong Python

Giả sử chúng ta có một mảng số nguyên, chúng ta cần tìm một mảng con liên tục sao cho, nếu chúng ta 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 theo. Chúng ta cần tìm mảng con ngắn nhất như vậy và xuất ra độ dài của nó. Vì vậy, nếu mảng là [2,6,4,8,10,9,15], đầu ra sẽ là 5. Mảng 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 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ụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau đây để 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