โปรแกรมค้นหาความยาวขั้นต่ำของการแยกอาร์เรย์ครั้งแรกที่มีองค์ประกอบที่เล็กกว่ารายการอื่นๆ ใน Python

สมมติว่าเรามีรายการตัวเลข nums เราต้องการแยกรายการออกเป็นสองส่วน part1 และ part2 เพื่อให้ทุกองค์ประกอบใน part1 มีค่าน้อยกว่าหรือเท่ากับทุกองค์ประกอบใน part1 เราต้องหาความยาวที่เล็กที่สุดของ part1 ที่เป็นไปได้ (ไม่ใช่ความยาว 0)

ดังนั้น ถ้าอินพุตเท่ากับ nums =[3, 1, 2, 5, 4] แล้วเอาต์พุตจะเป็น 3 เพราะเราสามารถแยกรายการได้เช่น part1 =[3, 1, 2] และ part2 =[5, 4].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• p :=จำนวนขั้นต่ำ
• s :=0
• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ
  • ถ้า nums[i] เหมือนกับ p แล้ว
    • s :=ฉัน
    • ออกมาจากวงจร
• p :=สูงสุดของรายการย่อยของ nums[จากดัชนี 0 ถึง s]
• ตอบ :=s
• สำหรับฉันในช่วง s + 1 ถึงขนาดของ nums - 1 ทำ
  • ถ้า nums[i]

  • ตอบ :=ฉัน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(nums):
   p = min(nums)
   s = 0
   for i in range(len(nums)):
      if nums[i] == p:
         s = i
         break
   p = max(nums[: s + 1])
   ans = s
   for i in range(s + 1, len(nums)):
      if nums[i] < p:
         ans = i
   return ans + 1

nums = [3, 1, 2, 5, 4]
print(solve(nums))

อินพุต

[3, 1, 2, 5, 4]

ผลลัพธ์

3