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

StackOverflow https://stackoverflow.com/questions/3466961

  •  28-09-2019
  •  | 
  •  

题

如何对列表中的元素进行排序 A 这样它们就遵循另一个（超集）列表的顺序 乙？假设没有重复项。

例如。 A 可能包含 [8 2 5 1] 和 乙 可能包含 [5 6 9 8 7 4 1 2 3]，所以我想排序 A 成为 [5 8 1 2]

我对高效且具有良好运行时复杂性的方法感兴趣。

有帮助吗？

解决方案

如果的乙是<强> A 下，我只转储的 A 到哈希表中，扫描的 B的一个超集并创建一个新的列表，其中我从插入的每一个元素的乙包含在哈希表中。用0-1（一）额外的内存和O（B）运行。

其他提示

以下是一些想法：

（在给定的时间复杂度下， n 的大小是 A 和 米 的大小是 乙. 。时间复杂度没有简化。）

  • 对于中的每个元素 乙, ，进行线性搜索 A 查看该元素是否存在于其中。如果是，则将其与第一个元素交换 A 尚未到位。 时间复杂度：氧(纳米)
  • 与上面相同，但首先将内容 A 进入有效的查找结构以避免线性搜索。 时间复杂度：O(n + m) 假设 O(1) 查找
  • 种类 乙. 。然后，对于每个元素 A, ，在其中找到它的索引（保证存在） 乙 使用二分查找。将此索引记录在与以下大小相同的辅助数组中 A. 。使用该索引数组作为排序比较器的输入 A. 时间复杂度：O((m log m) + (n log n) + (n log n))
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top