数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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，在右侧插入无穷大
- A，B := 两个新的空列表
- p := 1，q:= arr 的大小 -2
- M := 0
- 当 p <= q 时，执行以下操作
- 如果 arr[p-1] <= arr[p]，则
- 将 arr[p] 插入 A 的末尾
- p := p + 1
- 否则，当 arr[q] <= arr[q+1] 时，则
- 将 arr[q] 插入 B 的末尾
- 当 A 不为空且 A 的最后一个元素 > B 的最后一个元素时，执行以下操作
- 从 A 中删除最后一个元素
- q := q - 1
- 否则，
- 退出循环
- M := M 和 A 的大小 + B 的大小的最大值
- 如果 arr[p-1] <= arr[p]，则
- 返回 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
更新于: 2021年10月4日
226 次浏览
广告