在Python中找到使数组排序的最大块的程序
假设我们有一个数组nums,我们必须将数组拆分成一些分区,并单独对每个分区进行排序。现在在将它们连接后,我们将得到一个排序过的数组。我们必须找出我们可以做出的最大分区数?
因此,如果输入为[3,2,4,5,5],则输出为4,因为我们可以将分区制作为[3,2],[4],[5],[5]。
要解决此问题,我们将按照以下步骤进行 −
- real:=对列表nums进行排序
-
p1:= 0,p2:= 1,c:= 0
-
无限地执行以下操作,执行
- flag:= 真
-
tmp:=对nums [从索引p1到p2-1的子列表进行排序]
-
for j in range 0 to size of tmp 执行
- 如果tmp [j]与real [p1 + j]不同,则执行
-
flag:=假
-
p2:= p2 + 1
-
退出循环
-
如果flag为真,则执行
-
p1:= p2
-
p2:= p2 + 1
-
c:= c + 1
-
如果p1与nums的大小相同或者p2> nums的大小,则
-
返回c
例子
让我们看一下以下实现,以获得更好的理解
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))
输入
{3,2,4,5,5}
输出
4