根据另一个列表定义的顺序对列表排序

Question

如何对列表中的元素进行排序A以便它们遵循另一个（超集）列表的排序B？假定没有重复。

E.g. 甲可能包含[8 2 5 1]和乙可能含有[5 6 9 8 7 4 1 2 3]，所以我想进行排序甲成为[5 8 1 2]

我很感兴趣的方式有效地做到这一点，并具有良好的运行时复杂性。

Answer 1

如果乙是一个的超集，我只希望转储一个到一个哈希表，扫描乙并创建一个新的列表，其中我插入的每一个元素从乙即包含在哈希表中。使用O（a）额外的内存和O（b）运行时。

Answer 2

这里有一些想法：（。在给出的时间复杂度，Ñ是大小甲和米是乙的大小的时间复杂性不简化）

• 对于每个元素在乙，执行甲线性搜索，以查看是否该元素存在于其中。如果是这样，请将其与A中尚未放置到位的第一个元素进行交换。 时间复杂度：O（nm）
• 同上，但首先将A的内容转换为高效的查找结构以避免线性搜索。 时间复杂度：O（n + m）假设O（1）查找
• 排序B。然后，对于A中的每个元素，使用二分搜索在B内找到其索引（其保证存在）。将该索引记录在与A相同尺寸的辅助阵列中。使用该指数数组作为比较器的输入，该比较器对A进行排序。 时间复杂度：O（（M登入）+（N日志N）+（N日志N））