在Python中找到需要删除的最短子数组以使数组排序

在Python中找到需要删除的最短子数组以使数组排序

假设我们有一个名为 arr 的数组,我们必须删除 arr 的一个子数组,以便 arr 中剩余的元素是非降序排列的。我们必须找到要删除的最短子数组的长度。

因此,如果输入如下 arr = [10,20,30,100,40,20,30,50],则输出将为 3,因为我们可以删除 [100, 40, 20],它是长度为 3 的最小子数组,通过删除这些,[10,20,30,30,50] 中的所有元素都是非降序排列的。

要解决这个问题,我们将遵循以下步骤:

  • n := arr 的大小
  • arr := 在 arr 左侧插入 0,在 arr 右侧插入无限大
  • A、B := 两个新的空列表
  • p := 1,q:= arr 的大小 -2
  • M := 0
  • while p <= q,执行
    • 如果 arr[p-1] <= arr[p],则
      • 将 arr[p] 插入到 A 的末尾
      • p := p + 1
    • 否则当 arr[q] <= arr[q+1],则
      • 将 arr[q] 插入到 B 的末尾
      • while A 不为空 and A 的最后一个元素 > B 的最后一个元素,执行
      • 从 A 中删除最后一个元素
      • q := q – 1
    • 否则,
      • 退出循环
    • M := A 的大小与 B 的大小之和的最大值
  • 返回 n – M

让我们看下面的实现,以获得更好的理解:

示例

def solve(arr):
   n = len(arr)
   arr = [0] + arr + [float("inf")]
   A,B=[],[]
   p,q=1,len(arr)-2
   M = 0
   while p <= q:
      if arr[p-1] <= arr[p]:
         A.append(arr[p])
         p += 1
      elif arr[q] <= arr[q+1]:
         B.append(arr[q])
         while A and A[-1] > B[-1]:
            A.pop()
         q -= 1
      else:
         break
      M = max(M, len(A)+len(B))
   return n - M
arr = [10,20,30,100,40,20,30,50]
print(solve(arr))

输入

[10,20,30,100,40,20,30,50]

输出

3

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程