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的大小
• 最大值 := n-1，最小值 := 0
• smaller := 一個大小為1000的陣列，並填充0
• smaller[0] := -1
• 對於範圍從1到n的i，執行：
  • 如果A[i] <= A[最小值]，則
    • 最小值 := i
    • smaller[i] := -1
  • 否則，
    • smaller[i] := 最小值
• greater := 一個大小為1000的陣列，並填充0
• greater[n-1] := -1
• 對於範圍從n-2到-1的i，遞減1，執行：
  • 如果A[i] >= A[最大值]，則
    • 最大值 := i
    • greater[i] := -1
  • 否則，
    • greater[i] := 最大值
• 對於範圍從0到n的i，執行：
  • 如果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(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)

Arnab Chakraborty

更新於：2020年8月28日

127 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習