将“弹出列表”转换为“索引列表”的高效算法

Question

假设我有一个项目列表：

[ A, B, C, D ]

并且还有一个“流行列表”：

[ 2, 0, 1, 0 ]

假设有一个函数 f(x, p) = y，可以将索引 p 从列表 x 中弹出并放入新列表 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？

- eatcrayons

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

- Matt Timmermans

---

目标是避免调用 f。 - eatcrayons

啊...但你所要求的做法就像是调用f一样。也许你只是想将x放入一个顺序统计树中，以使f更快。 - Matt Timmermans

谢谢您的建议，但我真的只想将弹出列表转换为索引列表，而不使用 f。我很惊讶它变得多么棘手。 - eatcrayons

我标记为“已接受”的答案回答了我提出的问题。然而，我也发现这个答案中的信息非常有用。 - eatcrayons

Answer 2

我写了一个小的JS片段来解释我的想法。该算法不是O（N），但可能是O（n ^ 2）。虽然它不需要执行 f ，但我不能百分之百确定它是否正常工作，但如果不行，这可能是建立在其上的一个想法。

您将反转弹出列表并对其进行迭代：

1. 将当前元素添加到新数组中
2. 检查以前添加的元素是否大于或等于当前元素。
   3. 如果为真，则增加相应的值。
3. 返回新填充的数组（已反转）。

大致顺序：

0 
0 1
0 1 0
1 2 0 (increment old values with >= 0)
1 2 0 2
1 3 0 2 (increment old values with >= 2)

const data = [2, 0, 1, 0];

function popToIdx(popList) {
    let arr = [],
        tmp = [...popList].reverse(); // 0 1 0 2

    for (let i = 0; i < tmp.length; i++) {
      arr[i] = tmp[i];
      for (let j = 0; j < i; j++) {
        if (arr[j] >= tmp[i]) {
          arr[j] += 1;
        }
      }
    }

    return arr.reverse();
}

console.log(popToIdx(data)) // 2 0 3 1

对于列表而言，情况也是一样的，因为在末尾添加一个新元素仍然只需要O(1)的时间复杂度，并且对于列表和数组的部分迭代也是相同的。

- claasic

---

这就是我想要的答案。我也考虑过这个...但不确定它是否适用于所有情况。但看到别人提出相同的想法是有验证作用的。谢谢！ - eatcrayons