algorithm - 有效的按示例排序算法

Question

假设我们有一个长度为 N 的对象数组(所有对象都具有相同的字段集)。

并且我们有一个长度为 N 的相同类型值的数组，它表示某个对象的字段(例如，表示 ID 的数字数组)。

现在我们要按第二个数组中表示的字段对对象数组进行排序，并且顺序与第二个数组中的顺序相同。

例如，这里有 2 个数组(如描述中所示)和预期结果:

A = [ {id: 1, color: "red"}, {id: 2, color: "green"}, {id: 3, color: "blue"} ]
B = [ "green", "blue", "red"]

sortByColorByExample(A, B) == 
    [ {id: 2, color: "green"}, {id: 3, color: "blue"}, {id: 1, color: "red"} ]

如何有效实现“样例排序”功能？我想不出比 O(N^2) 更好的了。

Answer 1

这是假设您有一个从 B 中的元素到 A 中的元素的双射

从 B 的元素到它们的位置 (O(N)) 构建一个映射(比如 M)

对于 A 的每个元素 (O(N))，访问映射以找到将其放入排序数组的位置 (O(log( N)) 具有 map 的高效实现)

总复杂度:O(NlogN) 时间和O(N) 空间