Giả sử chúng ta có một số mảng, chúng ta phải chia mảng thành một số phân vùng và sắp xếp riêng từng phân vùng. Bây giờ sau khi nối chúng, chúng ta sẽ nhận được một mảng đã được sắp xếp. Chúng tôi phải tìm số lượng phân vùng tối đa mà chúng tôi có thể tạo ra?
Vì vậy, nếu đầu vào là [3,2,4,5,5], thì đầu ra sẽ là 4, vì chúng ta có thể tạo các phân vùng như [3,2], [4], [5], [5].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
real:=sắp xếp các số trong danh sách
-
p1:=0, p2:=1, c:=0
-
Làm những điều sau vô hạn, hãy làm
-
flag:=True
-
tmp:=sắp xếp danh sách con gồm các số [từ chỉ mục p1 đến p2-1]
-
đối với j trong phạm vi 0 đến kích thước của tmp, thực hiện
-
nếu tmp [j] không giống với thực [p1 + j] thì
-
cờ:=Sai
-
p2:=p2 + 1
-
đi ra từ vòng lặp
-
-
nếu cờ là true thì
-
p1:=p2
-
p2:=p2 + 1
-
c:=c + 1
-
-
nếu p1 giống với kích thước của nums hoặc p2> kích thước của nums, thì
-
trả lại c
-
-
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
def solve(nums):
real=sorted(nums)
p1,p2,c=0,1,0
while True:
flag=True
tmp=sorted(nums[p1:p2])
for j in range(len(tmp)):
if tmp[j]!=real[p1+j]:
flag=False
p2+=1
break
if flag:
p1,p2=p2,p2+1
c+=1
if p1==len(nums) or p2>len(nums):
return c
nums = [3,2,4,5,5]
print(solve(nums)) Đầu vào
{3,2,4,5,5}
Đầu ra
4