在 O(m sqrt(n)) 时间内将元素移动到列表前面的算法

Question

给定一个数字n，初始列表是(即初始列表已排序并包含从0到n-1的元素):

[0, 1, 2, ... n - 1]

输入是一个 m 数字序列。对于输入中的每个数字，将数字移动到列表的前面，并打印出该数字的索引。

例如:

n = 5:

输入:

3 3 4 2

输出:

3 0 4 4

解释:给定 n = 5，初始列表为

[0, 1, 2, 3, 4]

我们首先将 3 移到前面。 3在列表中的索引为3。

[3, 0, 1, 2, 4]

然后我们再次将 3 移到前面。因为已经在前面，所以索引为0。

[3, 0, 1, 2, 4]

然后，我们将 4 移到前面。 4的索引是4。

[4, 3, 0, 1, 2]

最后，我们将 2 移到前面。 2的索引是4。

[2, 4, 3, 0, 1]

我通过为每次移至前端线性搜索元素索引轻松实现了 O(mn) 解决方案。但是，我想不出在所需时间复杂度 O(m sqrt(n)) 内执行此操作的方法。

我想也许因为我们不需要在移动到前端之后返回实际列表，我们可以以某种方式利用它来减少工作量。也许一些额外的数据结构可能会有所帮助？

Answer 1

O(m√n) 对我来说有点奇怪，但你可以得到O( m log n) — 通过采用平衡的二叉搜索树结构(例如红黑树)而不是使用文字列表，渐近效果更好。

具体来说，你需要一个普通的二叉树结构，加上:

• 节点具有“子树大小”属性。
  • 如果您从根开始并导航，这将让您在 O(log n) 时间内计算节点的相对位置(= 列表索引)
• 不是让节点按照它们的实际值(0 到 n-1)排序，而是每个节点都有一个“标识符”。每次我们将一个节点移动到列表的开头时，我们将其标识符设置为比我们之前为任何节点使用的更小的数字(例如 0，然后是 -1，然后是 -2，等等)。所以我们通过这个“标识符”来保持节点的顺序。
  • 这将允许您从树的根导航到仅给出其标识符的节点。
  • 加上前面的内容，您可以在 O(log n) 时间内计算节点的相对位置，给定其“标识符”。
• 从值到当前节点“标识符”的映射。 (由于您的值方便地介于 0 到 n−1 之间，因此这可以只是一个整数数组。)
  • 加上前面的内容，您可以在 O(log n) 时间内计算节点的相对位置，仅给出其值。
  • 事实上，我们甚至不需要将值包含在二叉树结构中；节点仅需要标识符。
• 重新平衡父节点的逻辑，当它们变得过于倾斜时，通过像红黑树一样“旋转”它们。这可以在 O(log n) 时间内完成，这是必不可少的，因为您将不断从树的各个部分删除节点并将它们移动到最左边的叶子，所以如果不加以纠正，树将很快变得非常不平衡。

您可以在 O(n) 时间内初始化树，并在 O(log n ) 时间。

不幸的是，这种方法涉及大量簿记，以保持所有尺寸的更新并保持一切平衡。这不会影响算法的复杂性，但会导致实现困惑。也许其他人可以想到更简单的东西？ (或者，也许其他人可以想到一些不那么“自定义”的东西，其中更多的簿记由现成的 java.util.TreeMap 或 std::map 处理 或者诸如此类的东西？)