algorithm - 合并未排序的集合

Question

假设我有两个集合：

A = [约翰、玛丽、弗兰克、伊莎贝尔、特蕾莎]

B = [麦迪逊、约翰、弗兰克、伊莎贝尔、鲍勃]

该算法应产生以下结果：

合并 = [麦迪逊、约翰、玛丽、弗兰克、伊莎贝尔、特蕾莎、鲍勃]

（虽然特蕾莎和鲍勃互换也可以）

换句话说，算法应该使用两个输入集合的现有排序来创建一个合并集合。理论上存在无限数量的可能元素，并且没有可以从中获取元素顺序的“主”列表。

对于我的用例，输入集合将相当小（通常少于 50 个项目），并且集合之间的大多数项目将相同，尽管不能保证。

这是一种已知类型的算法吗？我一直在寻找合并算法，但大多数都在谈论有序列表及其性能优化。

- - - 编辑 - - -

再举几个例子：

第一个附加示例：A = [John, Mary, Frank, Isabel, Teresa, Robert, Bob, Anna, Tessa, Philip] B = [John, Mary, Robert, Bob, Philip, Nicholas] MERGE = [John, Mary, Frank 、伊莎贝尔、特蕾莎、罗伯特、鲍勃、安娜、泰莎、菲利普、尼古拉斯]

（因此算法应该推断 Nicholas 应该位于 Philip 之后，因为在集合 B 中也是如此）

第二个附加示例：A = [约翰，玛丽，弗兰克，伊莎贝尔，特蕾莎，罗伯特，鲍勃，安娜，泰莎，菲利普] B = [贝蒂，约翰，鲍勃，菲利普，尼古拉斯，鲍里斯] MERGE = [贝蒂，约翰，玛丽、弗兰克、伊莎贝尔、特蕾莎、罗伯特、鲍勃、安娜、泰莎、菲利普、尼古拉斯、鲍里斯]

（因此算法应该推断出 Betty 应该位于 John 之前，Nicholas & Boris 位于 Philip 之后）

标签： algorithmarray-merge

Answer 1

这是拓扑排序的一种变体，关系x < yifx出现y在任一列表之前。

只要有可能，此算法就会生成合并列表：

• 如果两个列表的头相同，则将该头添加到结果中，并将其从两个列表中删除。
• 如果任一列表的头部不在另一个列表中，则将其添加到结果中，并将其从所在的列表中删除。
• 否则，没有结果可以保留两个列表中元素的顺序。

您可以通过为列表中剩余元素的每个列表保留一个集合，或者为每个列表构建一个映射，将元素映射到列表中的索引，从而提高效率——即 O(n) 时间。