小编pin*_*guo的帖子

我有一组数字,例如:

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 …