Python程序：查找使数组排序的最大块数

假设我们有一个数组 nums，我们需要将其拆分成若干个分区，并分别对每个分区进行排序。现在，将这些分区连接起来，我们将得到一个排序后的数组。我们需要找到我们可以创建的最大分区数？

因此，如果输入类似于 [3,2,4,5,5]，则输出将为 4，因为我们可以创建诸如 [3,2]、[4]、[5]、[5] 之类的分区。

为了解决这个问题，我们将遵循以下步骤：

• real:= 对列表 nums 进行排序

• p1 := 0, p2 := 1, c := 0

• 无限循环执行以下操作：

  • flag:= True

  • tmp:= 对 nums[从索引 p1 到 p2-1] 的子列表进行排序

  • 对于 j 从 0 到 tmp 的大小，执行以下操作：

    • 如果 tmp[j] 与 real[p1+j] 不相同，则

      • flag:= False

      • 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

Arnab Chakraborty

更新于： 2021年10月8日

167 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习