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

สมมติว่าเรามีอาร์เรย์ที่มี N ตัวเลข เราต้องตรวจสอบว่ามี 3 องค์ประกอบที่ทำให้ b[i] < b[j] < b[k] และ i < j < k ในเวลาเชิงเส้น (O(n)) หากมีทริปเล็ตหลายชุด ให้พิมพ์ชุดใดชุดหนึ่ง

ตัวอย่าง

หากอินพุตคือ [13, 12, 11, 6, 7, 3, 31] ผลลัพธ์จะเป็น [6, 7, 31]

ขั้นตอนการแก้ปัญหา

1. n := ขนาดของ A
2. maximum := n-1, minimum := 0
3. smaller := อาร์เรย์ขนาด 1000 เติมด้วย 0, smaller[0] := -1
4. ลูป i จาก 1 ถึง n:
   • ถ้า A[i] <= A[minimum] ให้ minimum := i และ smaller[i] := -1
   • อื่นๆ ให้ smaller[i] := minimum
5. greater := อาร์เรย์ขนาด 1000 เติมด้วย 0, greater[n-1] := -1
6. ลูป i จาก n-2 ถึง -1 ลดทีละ 1:
   • ถ้า A[i] >= A[maximum] ให้ maximum := i และ greater[i] := -1
   • อื่นๆ ให้ greater[i] := maximum
7. ลูป i จาก 0 ถึง n:
   • ถ้า smaller[i] != -1 และ greater[i] != -1 ให้คืนค่า A[smaller[i]], A[i], A[greater[i]]
8. คืนค่า "Nothing"

การใช้งาน

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)