在Python中找到线性时间中大小为3的排序子序列

假设我们有一个N个数字的数组，我们必须检查3个元素是否在线性（O(n)）时间内b [i] <b [j] <b [k]和i <j <k。如果有多个这样的三胞胎，则打印其中任何一个。

因此，如果输入类似于[13，12，11，6，6，7，3，31]，那么输出将为[6,7,31]

为了解决这个问题，我们将遵循以下步骤-

• n：= A的大小

• 最大值：= n-1，最小值：= 0

• 更小：=大小为1000的数组，并用0填充

• 较小[0]：= -1

• 对于1到n范围内的i，执行

• 更小[i]：=最小值

• 最低：=我

• 小[i]：= -1

• 如果A [i] <= A [最小值]，则

• 除此以外，

• 更大：=大小为1000的数组，并用0填充

• 更大[n-1]：= -1

• 对于范围在n-2到-1之间的i，将其减小1，

• 更大[i]：=最大值

• 最大：=我

• 更大[i]：= -1

• 如果A [i]> = A [最大]，则

• 除此以外，

• 对于0到n范围内的i，执行

• 返回A [smaller [i]]，A [i]，A [greater [i]]

• 如果更小[i]与-1不相同，而更大[i]与-1不相同，则

• 返回“无”

示例

让我们看下面的实现以更好地理解-

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)