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

请教一个算法问题,关于合并数据的操作

  •  
  •   goinghugh · 2019-01-31 11:43:27 +08:00 · 2607 次点击
    这是一个创建于 1883 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有个 list 内嵌了 set, 结构如下:

    
    [
    	{1,2,3}
    	{2,3}
    	{3,5}
    	{10,15}
    ]
    

    定义: 如果一个 set 和另外的 set 有重复的元素,则表示这几个 set 是同一 group

    对于输入:

    
    [
    	{1,2,3}
    	{2,3}
    	{3,5}
    	{10,15}
    ]
    

    输出应该是:

    [
    {1,2,3,5}
    {10,15}
    ]
    

    写一个合并 group 操作时遇到的这个问题,感觉和 leecode 上的 friend circle 有点像,但是他的是矩阵,我的是嵌套的结构。 求组大佬指点一二或者提醒一下类似的算法,我去借鉴一下解决思路,不用直接给我答案,谢谢~

    24 条回复    2019-02-03 12:57:53 +08:00
    msg7086
        1
    msg7086  
       2019-01-31 12:03:25 +08:00   ❤️ 1
    遍历数组,将每个 set 中的元素放进字典里,做成
    a = {1,2,3}
    字典 {1=>&a, 2=>&a, 3=>&a}的效果。
    如果字典里已经有对应的元素了,先合并 set,再继续添加。
    即 b = {3,5},因为 3 已经有了,所以把 b 并入 a,变成
    a = {1,2,3,5}
    字典 {1=>&a, 2=>&a, 3=>&a, 5=>&a}
    一直跑完以后,把字典里的值对象去重就是结果了。
    leiuu
        2
    leiuu  
       2019-01-31 12:07:45 +08:00   ❤️ 1
    union-find
    goinghugh
        4
    goinghugh  
    OP
       2019-01-31 12:56:00 +08:00
    @msg7086 十分感谢,没想到用字典,另外问句,这是什么语言?
    msg7086
        5
    msg7086  
       2019-01-31 12:58:57 +08:00
    Ruby。

    另外这里我想了很久,觉得还是用二级引用来做比较好,也就是 {key => (ref => array)} 这样的做法,这样替换数组只要把引用的 ref 对象里的数据换掉就行了,比 array.replace 和遍历字典分别替换都要方便些。
    8cbx
        6
    8cbx  
       2019-01-31 13:05:00 +08:00
    并查集???
    layorlayor
        7
    layorlayor  
       2019-01-31 14:00:54 +08:00
    6L 说的对
    linxiaoziruo
        8
    linxiaoziruo  
       2019-01-31 14:19:43 +08:00
    @msg7086 你这个算法的时间复杂度也是 O(n),n 是所有集合的元素个数。本质上还是线性遍历。我觉得楼主可能是要一个时间复杂度小于 O(n)的算法,也就是不要遍历。
    linxiaoziruo
        9
    linxiaoziruo  
       2019-01-31 14:23:55 +08:00
    @8cbx 不是并查集。这个算法的核心问题在于怎么求交集,并查集的核心思想是解决连通图的问题。这是两个问题。
    fzy0728
        10
    fzy0728  
       2019-01-31 14:41:17 +08:00
    并查集没问题,本身就是存在连通关系。
    感觉 1l 的存在一些问题
    [
    (1,2,3)

    ]
    fzy0728
        11
    fzy0728  
       2019-01-31 14:45:40 +08:00
    [
    (1,2,3)
    (6,7)
    (3,6)
    ]
    如果 1,2,3 对应 a,之后 6,7 对应 b,在 3,6 时需要将前两个集合进行合并,就会需要 7 也变成统一的标签。不然只是在某个 key 下加入了一个元素,最后结果就会变成 1,2,3,6 -》 a ,7-》 b
    fzy0728
        12
    fzy0728  
       2019-01-31 14:52:40 +08:00
    linxiaoziruo
        13
    linxiaoziruo  
       2019-01-31 14:52:40 +08:00
    @fzy0728 用并查集分组,然后合并是行不通的。关键就是并查集不能解决这个合并问题,想合并必须先求交集,想求交集就必须两个数组都遍历,假设有数组 A(m), B(n),则合并一次的时间是 m*n。
    linxiaoziruo
        14
    linxiaoziruo  
       2019-01-31 14:54:22 +08:00
    我觉得用 bitmap 可以解决这个问题。
    对于 A,B 两个数组,用 BitMap 来存储,比如:
    A:001011010101011100000010...
    B:010101101100010110101110...
    然后用 A&B,再求出结果中 1 的个数即可。这样既保证了空间高效,也保证了时间高效。
    aijam
        15
    aijam  
       2019-01-31 14:54:43 +08:00
    shidenggui
        16
    shidenggui  
       2019-01-31 15:00:52 +08:00
    https://gist.github.com/shidenggui/933213ff4d1abfa142923ed766544112

    用 union-find 写了下,感觉并不是最优的。
    layorlayor
        17
    layorlayor  
       2019-01-31 15:01:47 +08:00
    对于一个数字,找出他在哪些集合出现过,再用并查集把这些集合合并。
    frazy
        18
    frazy  
       2019-01-31 15:26:02 +08:00
    每个元素遍历,每个元素索引,如果同一 set 存在索引,添加。。看代码
    const list = [
    [1,2,3],
    [2,3],
    [3,5],
    [10,15],
    ];
    let groups = [];
    let dict = {};
    list.forEach(set=>{
    let group = null;
    set.forEach(e => {
    if (dict[e]) {
    group = dict[e];
    } else {
    if (group) {
    group.push(e);
    dict[e] = group;
    } else {
    dict[e] = set;
    }
    }
    });
    if (!group) {
    groups.push(set);
    }
    });
    console.log('groups', groups);
    frazy
        19
    frazy  
       2019-01-31 15:31:55 +08:00
    我的错了
    nlzy
        20
    nlzy  
       2019-01-31 15:47:37 +08:00
    princelai
        21
    princelai  
       2019-01-31 15:55:40 +08:00
    如果输入是[
    {1,2}
    {2,3}
    {3,5}
    {10,15}
    ]

    那么结果应该是[
    {1,2,3}
    {2,3,5}
    {10,15}
    ]
    hitmanx
        22
    hitmanx  
       2019-01-31 18:23:00 +08:00
    @linxiaoziruo

    bitmap 如果碰到上限大就不好弄了,比如元素最大可以是 U32 甚至 U64 ;另外生成 bitmap 也需要 O(n),n 为全部元素数量(我感觉不可能有低于 O(n)的算法,因为最坏情况下至少所有元素都需要遍历一次)
    shidenggui
        23
    shidenggui  
       2019-02-01 09:09:35 +08:00
    对昨天写的 union find 做了下 performance,时间复杂度约等于 O(N),下面是结果。具体测试代码附在上面的 gist 里了。

    union-find:
    K rows: 100 N: 63196 time: 79 T(N)/O(N): 799
    K rows: 200 N: 126404 time: 149 T(N)/O(N): 848
    K rows: 400 N: 252847 time: 298 T(N)/O(N): 848
    K rows: 800 N: 506194 time: 600 T(N)/O(N): 843
    K rows: 1600 N: 1012045 time: 1214 T(N)/O(N): 833
    K rows: 3200 N: 2024459 time: 2481 T(N)/O(N): 815
    8cbx
        24
    8cbx  
       2019-02-03 12:57:53 +08:00
    感觉并查集完美解决了啊,初始化:每个元素的父是自己;然后对于每一组中的每一个元素,先判断自己是否已经有非自己的父,有则把这组的第一个元素和他的父并,否则把自己并到这组的第一个元素下面
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1010 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 19:59 · PVG 03:59 · LAX 12:59 · JFK 15:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.