資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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
更新於： 2021年10月8日
167 次檢視
廣告