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)了，还有在最前面插入也是这样。不知道大家有什么好办法吗，谢谢大家帮助。
This topic created in 3226 days ago, the information mentioned may be changed or developed.
4 replies • 2017-07-23 15:20:29 +08:00
 |
1
scinart Jul 18, 2017 via iPhone
看了题，说说我的想法(手机码字)：
若 list item 是有 Eq 但是没 Ord，即无法比较大小，显然 del 复杂度是线性的。若 list item 可重复，不难推出 del 复杂度也是线性的，故假定 list item 可比较，无重复。 在这种情况下应该是可以做到的，用一个普通的双向链表，再用哈希记录哪些元素在当前列表里，再用一个平衡树记录每个元素的 index。 然后 add 时从平衡树中找到索引所在链表的位置，插入元素，更新平衡树，更新哈希 del item 时从哈希找到平衡树的位置，del idx 时直接找平衡树的位置，再从平衡树找到双向链表的位置，删除之，更新平衡树，更新哈希。 平衡树应该是能做到的，表达有限，你体会一下？ |
|
2
scinart Jul 18, 2017 via iPhone  1
我去 segmentfault 已经有人答了，刚看到，~ ~
|
 |
3
lgqfhwy OP 你好，谢谢你的回复。你的这个其实有点问题的，直接记录每个元素的 index ,当插入的时候，就需要把所有在 index 后的元素更新，这样就慢了。
具体可以看 segmentfault 的回复，就是我采纳的那一个，说的很好，当然还是有些细节上不够完善，具体实现的话要自己想些方法。 有问题再联系。 |
Select Language