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

请教大家一道算法题?

  •  
  •   ihourui · 2020-05-10 22:39:39 +08:00 · 2567 次点击
    这是一个创建于 1474 天前的主题,其中的信息可能已经有所发展或是发生改变。
    c++里有一堆 pair, 比如<1,2>, <3,2>, <3,6>, <6,3>, <6,4>, <5,8>, <9,8>, <10,12>, <12,11>, 把 pair 里不管第一个还是第二个元素相同的 pair 划分为一组, 最后的结果是[<1,2>, <3,2>, <3,6>,<6,3>, <6,4>], [<5,8>, <9,8>], [<10,12>, <12,11>],我自己是用循环实现的,但是 pair 多的时候效率太差, 请问一下各位有什么好的算法可以实现吗?谢谢!
    11 条回复    2020-05-11 09:18:38 +08:00
    siyemiaokube
        1
    siyemiaokube  
       2020-05-10 22:46:57 +08:00 via iPhone
    谢不邀,不确定你说的啥

    方法一:建图,二元组就是一条边。缺点是不适合动态维护

    方法二:hash+并查集。适合动态维护,效率略低。
    luckyrayyy
        2
    luckyrayyy  
       2020-05-10 22:48:25 +08:00
    把所有 pair 用图来表示,然后判断里面一共有几组连通图? dfs 搜?
    siyemiaokube
        3
    siyemiaokube  
       2020-05-10 22:51:22 +08:00 via iPhone
    update:不需要建图,直接把一个 pair<a,b>当成并查集里的 merge ( a,b )就行了
    xupefei
        4
    xupefei  
       2020-05-10 22:59:10 +08:00
    一楼说的对。
    把 pair 中的每个元素作为 key 建立哈希表,然后用 union-find 。时间复杂度 O(\log n)。
    ksedz
        5
    ksedz  
       2020-05-10 23:06:23 +08:00
    至少要循环遍历一次的

    如果你是指多次操作慢可以考虑加结果缓存或在产生时打标记
    Allianzcortex
        6
    Allianzcortex  
       2020-05-10 23:22:48 +08:00
    1 楼 + 1,Hash + 并查集,楼主的需求和这道题很相似: https://leetcode-cn.com/problems/baby-names-lcci/
    QingchuanZhang
        7
    QingchuanZhang  
       2020-05-11 01:12:52 +08:00
    lithbitren
        8
    lithbitren  
       2020-05-11 05:31:27 +08:00
    楼里的这两道并查集题的最短 py 解法都是俺写的,时间上一道 100%一道 98%,理论上 c++也可以按照相同原理实现。
    ihourui
        9
    ihourui  
    OP
       2020-05-11 07:46:37 +08:00
    @siyemiaokube 谢谢,我试一下你的做法,非常感谢!
    ihourui
        10
    ihourui  
    OP
       2020-05-11 07:48:20 +08:00
    @luckyrayyy 我就是用 dfs 递归搞的,但是 pair 多的时候时间消耗很大。
    sarvatathagata
        11
    sarvatathagata  
       2020-05-11 09:18:38 +08:00
    如果没有修改的话,可以做到线性。先与一楼的做法一样 hash,然后对于出现过的每一个 first 元素和每一个 second 元素建虚点,<a,b>和第一类虚点{a}还有第二类虚点{b}连边。然后跑 dfs 就可以线性了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5533 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 01:57 · PVG 09:57 · LAX 18:57 · JFK 21:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.