首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

如何解决这道算法题

  •  
  •   lgqfhwy · 2017-07-16 14:39:35 +08:00 · 878 次点击
    这是一个创建于 875 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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)了,还有在最前面插入也是这样。不知道大家有什么好办法吗,谢谢大家帮助。

    4 回复  |  直到 2017-07-23 15:20:29 +08:00
        1
    scinart   2017-07-18 23:33:23 +08:00 via iPhone
    看了题,说说我的想法(手机码字):

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

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

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

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

    平衡树应该是能做到的,表达有限,你体会一下?
        2
    scinart   2017-07-18 23:49:57 +08:00 via iPhone   ♥ 1
    我去 segmentfault 已经有人答了,刚看到,~ ~
        3
    lgqfhwy   2017-07-19 23:24:20 +08:00
    你好,谢谢你的回复。你的这个其实有点问题的,直接记录每个元素的 index ,当插入的时候,就需要把所有在 index 后的元素更新,这样就慢了。
    具体可以看 segmentfault 的回复,就是我采纳的那一个,说的很好,当然还是有些细节上不够完善,具体实现的话要自己想些方法。
    有问题再联系。
        4
    scinart   2017-07-23 15:20:29 +08:00 via iPhone
    @lgqfhwy 我去有问题再联系?我一脸黑人问号,,,

    我和想法和 segmentfault 答案一样的,手机码字表达有限,但平衡树里节点的位置自然就是 index,楼主已知答案,看我答案时为啥还报着你的记录 index 的思想不放?
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2277 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 26ms · UTC 08:28 · PVG 16:28 · LAX 00:28 · JFK 03:28
    ♥ Do have faith in what you're doing.