สมมติว่าเรามีจำนวนอาร์เรย์ เราต้องแยกอาร์เรย์ออกเป็นพาร์ติชั่นจำนวนหนึ่ง และจัดเรียงแต่ละพาร์ติชั่นแยกกัน ตอนนี้หลังจากเชื่อมเข้าด้วยกันแล้วเราจะได้อาร์เรย์ที่จัดเรียงมาหนึ่งชุด เราต้องหาจำนวนพาร์ติชั่นสูงสุดที่เราสามารถทำได้หรือไม่?
ดังนั้นหากอินพุตเป็น [3,2,4,5,5] เอาต์พุตจะเป็น 4 เนื่องจากเราสามารถสร้างพาร์ติชั่นได้เช่น [3,2], [4], [5], [5]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
จริง:=เรียงลำดับรายการจำนวน
-
p1 :=0,p2 :=1, c :=0
-
ทำสิ่งต่อไปนี้อย่างไม่สิ้นสุด ทำ
-
ธง:=จริง
-
tmp:=เรียงลำดับรายการย่อยของ nums[จากดัชนี p1 ถึง p2-1]
-
สำหรับ j ในช่วง 0 ถึงขนาดของ tmp ให้ทำ
-
ถ้า tmp[j] ไม่เหมือนกับของจริง[p1+j] แล้ว
-
ธง:=เท็จ
-
p2 :=p2 + 1
-
ออกจากวง
-
-
ถ้าแฟล็กเป็นจริง
-
p1 :=p2
-
p2:=p2+1
-
ค :=ค + 1
-
-
ถ้า p1 เท่ากับขนาดของ nums หรือ p2> ขนาดของ nums แล้ว
-
กลับค
-
-
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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
