V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
alex321
V2EX  ›  算法

比较复杂的别名字典去重优化

  •  
  •   alex321 · 2021-09-03 01:20:42 +08:00 · 1163 次点击
    这是一个创建于 937 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有几万个别名字典,存在如下情形: {A:A1} {A1:A2} {A3:A4} {A2:A3} {B4:B3} {B1:B4} {B4:B} {B3:B2} {B2:B5}

    想构造出如下结果: {A:(A1,A2,A3,A4)} {B:(B1,B2,B3,B4,B5)}

    目前我想到的办法很傻瓜,多重遍历。想请教下有什么高效的法子呢?

    5 条回复    2021-09-03 11:09:58 +08:00
    RecursiveG
        1
    RecursiveG  
       2021-09-03 03:09:16 +08:00   ❤️ 1
    并查集
    geelaw
        2
    geelaw  
       2021-09-03 04:30:38 +08:00 via iPhone   ❤️ 1
    离线问题计算无向图的连通分量即可(比如 BFS ),在线问题用并查集。
    whusnoopy
        3
    whusnoopy  
       2021-09-03 08:37:46 +08:00   ❤️ 1
    有一个问题细节待明确,别名集合好理解,在同一个联通子图里就好,别名的 key 怎么定?最短?首次出现?看样例里 B 并不是在 Bx 里第一次出现的

    这个不管离线在线应该都是并查集更快,离线构建图的过程也是有时间空间开销的
    alex321
        4
    alex321  
    OP
       2021-09-03 09:56:12 +08:00
    @whusnoopy #3 key 可以不定。给集合元组也可以的。
    (A,A1,A2,A3,A4)
    (B,B1,B2,B3,B4,B5)
    whusnoopy
        5
    whusnoopy  
       2021-09-03 11:09:58 +08:00   ❤️ 1
    @alex321

    那这就是一个标准并查集的问题了,先便利一遍构建并查集,再便利一遍按并查集结果输出。针对你的样例写了段 Python 代码

    https://gist.github.com/whusnoopy/c9b43dde396aa57f61318c09870d5517
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3209 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 11:36 · PVG 19:36 · LAX 04:36 · JFK 07:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.