在Python中找到使数组排序的最大块的程序

在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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程