如何在O(lg(n))内实现这些API ?

原问题的[网址链接]1
http://algs4.cs.princeton.edu...

List. Implement the following list operations: size(), addFront(item),
addBack(item), delFront(item), delBack(item), contains(item),
delete(item), add(i, item), delete(i), iterator(). All operations
should be efficient (logarithmic). Hint: use two symbol tables, one to
find the ith element in the list efficiently, and the other to
efficiently search by item. Java's List interface contains these
methods, but does not supply any implementation that supports all ops
efficiently.

我觉得是不可能在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)了,还有在最前面插入也是这样。不知道大家有什么好办法吗,谢谢大家帮助。
具体要求
图片描述

阅读 1.6k
评论
    2 个回答

    可以用TreeMap或TreeSet来模拟List,这样算法复杂度就是O(logN)的。当然这有点难度。

    另外可以研究下一种叫TreeList的结构,详情参阅:
    https://commons.apache.org/pr...
    它并非像TreeMap一样用红黑树,而是用另一种平衡树:AVL树

      相似问题
      推荐文章