[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, 3, 0, 1, 2]
最后,我们向前移动2.指数2是4.
[2, 4, 3, 0, 1]
我通过线性搜索每个从前到前移动的元素的索引,轻松实现了O(mn)解决方案.但是,我想不出在所需的时间复杂度O(m sqrt(n))内做到这一点的方法.
我想也许因为我们不需要在移动到前面之后返回实际列表,我们可以通过某种方式利用它来减少工作量.也许一些额外的数据结构可能有所帮
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或诸如此类的？处理的？)