找到具有给定排名的所有固定长度的子阵列

Question

我有一组数字,例如:

A = [1, 5, 2, 4, 3]

和一个确定排名的数组,例如:

B = [0, 2, 1]

我的目标是找到A"服从"等级B的所有子阵列.如果子阵列服从等级,则意味着子阵列的第i个最小元素必须具有B[i]其(子阵列)索引.因此,对于要匹配的子阵列,其中的最小元素必须位于位置0,第二个小元素必须位于位置2,并且最大元素必须位于位置1.

例如,这里有两个与排名匹配的A子阵列:[1,5,2](因为A [0] <A [2] <A [1])和[2,4,3].

到目前为止,我已经设法找到一个解决方案,其中O(mn)(m是len(A)和n是len(B))时间复杂度,它遍历所有长度为3的子数组并验证它们是否正确排序:

A = [1, 5, 2, 4, 3]
B = [0, 2, 1]
m = len(A)
n = len(B)
for i in range(m - n + 1):
    current_subarray = A[i:i + n]
    # we now do n - 1 comparaisons to check whether the subarray is correctly ordered.
    for B_index in range(n - 1):
        if current_subarray[B[B_index]] > current_subarray[B[B_index + 1]]:
            break
    else:
        print("Subarray found:", current_subarray)

结果:

Subarray found: [1, 5, 2]
Subarray found: [2, 4, 3]

这有效,但我想知道是否有更好的优化算法(更好O(mn))来完成这项任务.

Answer 1

您可以循环A并检查生成的子数组：

A, B = [1, 5, 2, 4, 3], [0, 2, 1]
def results(a, b):
   _l = len(b)
   for c in range(len(a)-_l+1):
     _r = a[c:c+_l]
     new_r = [_r[i] for i in b]
     if all(new_r[i] < new_r[i+1] for i in range(len(new_r)-1)):
       yield _r

print(list(results(A, B)))

输出：

[[1, 5, 2], [2, 4, 3]]