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)

更新于：2020年8月28日

127 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告