查找要删除的最短子数组以使数组在 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

  • 米:= 0

  • 而 p <= q,做

    • 从循环中出来

    • 在 B 的末尾插入 arr[q]

    • 当 A 不为空且 A 的最后一个元素 > B 的最后一个元素时,做

    • q := q - 1

    • 从 A 中删除最后一个元素

    • 在 A 的末尾插入 arr[p]

    • p := p + 1

    • 如果 arr[p-1] <= arr[p],则

    • 否则当 arr[q] <= arr[q+1] 时,则

    • 除此以外,

    • M := 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 中排序的程序 的全部内容, 来源链接: utcz.com/z/349098.html

    回到顶部