Python - रैखिक समय में आकार 3 का सॉर्टेड सबसीक्वेंस ढूंढना

मान लीजिए हमारे पास N नंबर्स की एक ऐरे है, हमें चेक करना है कि क्या 3 एलिमेंट्स ऐसे हैं कि b[i] < b[j] < b[k] और i < j < k रैखिक (O(n)) समय में। यदि ऐसे कई ट्रिपलेट्स हैं, तो उनमें से कोई भी एक प्रिंट करें।

तो, यदि इनपुट [13, 12, 11, 6, 7, 3, 31] जैसा है, तो आउटपुट [6, 7, 31] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• n := A का आकार
• maximum := n-1, minimum := 0
• smaller := आकार 10000 की ऐरे, 0 से भरी
• smaller[0] := -1
• i को 1 से n तक रेंज में, करें
  • यदि A[i] <= A[minimum], तो
    • minimum := i
    • smaller[i] := -1
  • अन्यथा,
    • smaller[i] := minimum
• greater := आकार 10000 की ऐरे, 0 से भरी
• greater[n-1] := -1
• i को n-2 से -1 तक, 1 से घटाते हुए, करें
  • यदि A[i] >= A[maximum], तो
    • maximum := i
    • greater[i] := -1
  • अन्यथा,
    • greater[i] := maximum
• i को 0 से n तक रेंज में, करें
  • यदि smaller[i] != -1 और greater[i] != -1, तो
    • A[smaller[i]], A[i], A[greater[i]] लौटाएं
• "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(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)