資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告