algorithm - 将 "pop list"转换为 "index list"的高效算法

Question

假设我有一个项目列表:

[ A, B, C, D ]

和一个“流行列表”:

[ 2, 0, 1, 0 ]

设 f(x,p) = y 是一个将 x 中的索引 p 弹出到新列表中的函数，y.

使用这个过程，你可以计算

f([ A, B, C, D ], [ 2, 0, 1, 0 ]) = [ C, A, D, B ]

但是，f 的成本是不切实际的，因为它从列表中弹出并重复加入剩余元素。

最好有一个算法，g，将弹出列表转换为索引列表，这样

g(p) = [ 2, 0, 3, 1]

这将允许有效地构建新列表。

是否有一个有效的算法，也许是 O(N)，可以用于实现 g？

Answer 1

最简单的方法是将 f 应用于索引列表:

g(p) = f([0, 1, ... length(p)-1], p)

(假设 length(p) 是索引的范围。否则使用适当的长度，或者在必要时动态增长)

这是 O(n^2)。您可以通过将 x 存储在顺序统计树而不是列表中来使其O(n log n):

https://en.wikipedia.org/wiki/Order_statistic_tree