ค้นหาลำดับย่อยที่จัดเรียงของขนาด 3 ในเวลาเชิงเส้นใน Python

สมมติว่าเรามีอาร์เรย์ที่มีตัวเลข N เราต้องตรวจสอบว่าองค์ประกอบ 3 อย่างนั้น b[i]

ดังนั้น หากอินพุตเป็น [13, 12, 11, 6, 7, 3, 31] เอาต์พุตจะเป็น [6,7,31]

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

• n :=ขนาดของ A
• สูงสุด :=n-1 ขั้นต่ำ :=0
• เล็กลง :=อาร์เรย์ขนาด 1000 และเติม 0
• เล็กกว่า[0] :=-1
• สำหรับฉันในช่วง 1 ถึง n ทำ
  • ถ้า A[i] <=A[ขั้นต่ำ] แล้ว
    • ขั้นต่ำ :=ฉัน
    • เล็กกว่า[i] :=-1
  • มิฉะนั้น
    • เล็กกว่า[i] :=ขั้นต่ำ
• มากกว่า :=อาร์เรย์ขนาด 1000 และเติมด้วย 0
• มากกว่า[n-1] :=-1
• สำหรับ i ในช่วง n-2 ถึง -1, ลดลง 1, ทำ
  • ถ้า A[i]>=A[สูงสุด] แล้ว
    • สูงสุด :=ผม
    • มากกว่า[i] :=-1
  • มิฉะนั้น
    • มากกว่า[i] :=สูงสุด
• สำหรับฉันในช่วง 0 ถึง n ให้ทำ
  • ถ้าเล็กกว่า[i] ไม่เหมือนกับ -1 และมากกว่า[i] ไม่เหมือนกับ -1 แล้ว
    • ส่งคืน A[เล็กกว่า[i]], A[i], A[มากขึ้น[i]]
• ส่งคืน "ไม่มีอะไร"

ตัวอย่าง

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

def find_inc_seq(A):
   n = len(A)
   maximum = n-1
   minimum = 0
   smaller = [0]*10000
   smaller[0] = -1
   for i in range(1, n):
      if (A[i] <= A[minimum]):
         minimum = i
         smaller[i] = -1
      else:
         smaller[i] = minimum
   greater = [0]*10000
   greater[n-1] = -1
   for i in range(n-2, -1, -1):
      if (A[i] >= A[maximum]):
         maximum = i
         greater[i] = -1
      else:
         greater[i] = maximum
   for i in range(0, n):
      if smaller[i] != -1 and greater[i] != -1:
         return A[smaller[i]], A[i], A[greater[i]]
   return "Nothing"
arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr) )

อินพุต

[13, 12, 11, 6, 7, 3, 31]

ผลลัพธ์

(6, 7, 31)