Chương trình tìm mảng phân vùng thành các khoảng riêng biệt trong Python

Giả sử chúng ta có một số mảng, chúng ta phải phân vùng nó thành hai mảng con khác nhau được gọi là trái và phải sao cho -

• Mỗi phần tử trong mảng con bên trái nhỏ hơn hoặc bằng mỗi phần tử trong mảng con bên phải.

• mảng con bên trái và bên phải không trống.

• mảng con bên trái có kích thước nhỏ nhất có thể.

Chúng ta phải tìm độ dài bên trái sau khi phân vùng như vậy.

Vì vậy, nếu đầu vào là nums =[5,0,3,8,6], thì đầu ra sẽ là 3 vì mảng bên trái sẽ là [5,0,3] và mảng con bên phải sẽ là [8,6].

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

• mx:=null, temp:=null, nmx:=null

• temp2:=0

• đối với mỗi tôi trong nums, hãy thực hiện

  • nếu mx giống với null thì

    • mx:=i

    • nmx:=i

    • temp:=temp2

    • temp2:=temp2 + 1

    • chuyển sang lần lặp tiếp theo

  • nếu tôi> =mx, thì

    • temp2:=temp2 + 1

    • nếu tôi> nmx, thì

      • nmx:=i

    • chuyển sang lần lặp tiếp theo

  • nếu không,

    • temp:=temp2

    • temp2:=temp2 + 1

    • mx:=nmx

    • chuyển sang lần lặp tiếp theo

• trả về nhiệt độ + 1

Ví dụ

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

def solve(nums):
   mx = None
   temp = None
   nmx = None
   temp2 = 0

   for i in nums:

      if(mx==None):
         mx = i
         nmx = i
         temp = temp2
         temp2+=1
         continue

      if(i>=mx):
         temp2+=1
         if(i>nmx):
            nmx = i
         continue

      else:
         temp = temp2
         temp2+=1
         mx = nmx
         continue

   return temp+1

nums = [5,0,3,8,6]
print(solve(nums))

Đầu vào

[5,0,3,8,6]

Đầu ra

3