如何对列表A的元素进行排序，以便它们遵循另一个（超集）列表B的排序？假设没有重复。
例如A可能包含 [8 2 5 1] 而B可能包含 [5 6 9 8 7 4 1 2 3]，所以我想将A排序为 [5 8 1 2]
我对有效且具有良好运行时复杂性的方法感兴趣。
问问题
582 次
2 回答
3
如果B是A的超集，我只需将A转储到哈希表中，扫描B并创建一个新列表，在其中插入B中包含在哈希表中的每个元素。使用 O(a) 额外内存和 O(b) 运行时间。
于 2010-08-12T11:17:05.313 回答
2
这里有一些想法：
（在给定的时间复杂度中，n是A的大小，m是B的大小。时间复杂度没有简化。）
- 对于B中的每个元素，对A进行线性搜索以查看该元素是否存在于其中。如果是这样，请将其与A中尚未放置到位的第一个元素交换。时间复杂度：O(nm)
- 同上，但首先将A的内容放入一个高效的查找结构中，以避免线性搜索。时间复杂度：O(n + m) 假设 O(1) 查找
- 排序B。然后，对于A中的每个元素，使用二进制搜索在B中找到其索引（保证存在） 。将此索引记录在与A大小相同的辅助数组中。使用该索引数组作为对A进行排序的比较器的输入。时间复杂度：O((m log m) + (n log n) + (n log n))
于 2010-08-12T11:21:37.887 回答