算法-顺序排列连续区域合并问题

算法-顺序排列连续区域合并问题

清晨说ぺ晚安 发布于 2017-03-20 字数 242 浏览 974 回复 1

假设有顺序排列的连续区域,共有两列,每列区域均顺序排序且互相之间不相交,求两列的区域交集,即:区域数列A:[2-5] [7-10] [15-25],数列B:[4-6] [8-9] [10-20],求出来的结果是[4-5] [8-9] [15-20],现有一个算法是O(m+n),请问有没有更好的效率?

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

灵芸 2017-10-04 1 楼

这个算法的基础是两路归并,O(M+N)应该是理论复杂度下限了。但是还是有可能结合具体程序的前置或后置算法信息做改进,或针对输入数据的更多特殊之处做改进。如果只有这么多信息,那就只能考虑在算法复杂度的常数部分改进了。