11赞
715
当前位置:  开发笔记 > 编程语言 > 正文

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

如何解决《找到具有给定排名的所有固定长度的子阵列》经验,谁能帮忙解答一下?

我有一组数字,例如:

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

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

B = [0, 2, 1]

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

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

到目前为止,我已经设法找到一个解决方案,其中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))来完成这项任务.

推荐阅读
devbox
飞跃星空2502906253
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved PHP1.CN 第一PHP社区 版权所有 京ICP备19059560号-4