是否有比 O(n^2) 更好的算法来重新排序列表 2 以匹配列表 1
列表 1:A B C D
列表 2:B D C A
注意:与列表 1 相比,列表 2 可以有更多、更少甚至完全不同的项目。
最佳答案
如果您可以为列表中的项目类型创建总排序,则可以通过对项目进行排序来为列表 1 创建索引。然后您可以使用该索引对列表 2 重新排序。该算法在时间上是 O(n log n),并且在空间上需要额外的 O(n)。
关于algorithm - 比较两个列表的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4305198/