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

server side programmingprogrammingpython

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

因此，如果输入为 [13, 12, 11, 6, 7, 3, 31]，则输出为 [6,7,31]

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

n := A 的大小
最大值 := n-1，最小值 := 0
较小值 := 大小为 1000 的数组，并用 0 填充
较小值[0] := -1
对于范围从 1 到 n 的 i，执行
- 如果 A[i] <= A[最小值]，则
  - 最小值 := i
  - smaller[i] := -1
- 否则，
  - smaller[i] := minimum
greater := 大小为 1000 的数组，并用 0 填充
greater[n-1] := -1
对于 n-2 到 -1 范围内的 i，减少 1，执行
- 如果 A[i] >= A[maximum]，则
  - maximum := 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) )