如何解决这道算法题

[lgqfhwy]

https://segmentfault.com/q/1010000010202695?_ea=2201957 大家帮我解答一下，谢谢！ 我觉得是不可能在 O(lgn)内全部实现的。两个 symbol table. 一个（ key = i (the index), value = Item), 另一个 (key = Item, value = i (the index). 这个快速查找倒是能在 O(1)实现，java HashMap 一般为 O(1), 这是最好情况，但是删除的时候，比如删除第 i 个，就需要把所有大于 i 的节点都更新一遍（全都减 1 ），这样就成了 O(n)了，还有在最前面插入也是这样。不知道大家有什么好办法吗，谢谢大家帮助。

[scinart]

看了题，说说我的想法(手机码字)：

若 list item 是有 Eq 但是没 Ord，即无法比较大小，显然 del 复杂度是线性的。若 list item 可重复，不难推出 del 复杂度也是线性的，故假定 list item 可比较，无重复。

在这种情况下应该是可以做到的，用一个普通的双向链表，再用哈希记录哪些元素在当前列表里，再用一个平衡树记录每个元素的 index。

然后 add 时从平衡树中找到索引所在链表的位置，插入元素，更新平衡树，更新哈希

del item 时从哈希找到平衡树的位置，del idx 时直接找平衡树的位置，再从平衡树找到双向链表的位置，删除之，更新平衡树，更新哈希。

平衡树应该是能做到的，表达有限，你体会一下？

[scinart]

我去 segmentfault 已经有人答了，刚看到，~ ~

[lgqfhwy]

你好，谢谢你的回复。你的这个其实有点问题的，直接记录每个元素的 index ,当插入的时候，就需要把所有在 index 后的元素更新，这样就慢了。
具体可以看 segmentfault 的回复，就是我采纳的那一个，说的很好，当然还是有些细节上不够完善，具体实现的话要自己想些方法。
有问题再联系。

[scinart]

@lgqfhwy 我去有问题再联系？我一脸黑人问号，，，

我和想法和 segmentfault 答案一样的，手机码字表达有限，但平衡树里节点的位置自然就是 index，楼主已知答案，看我答案时为啥还报着你的记录 index 的思想不放？