V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
zealinux
V2EX  ›  Python

Python 怎么实现归并集合功能?

  •  
  •   zealinux · 2019-03-13 16:26:26 +08:00 · 2268 次点击
    这是一个创建于 2093 天前的主题,其中的信息可能已经有所发展或是发生改变。

    比如

    输入:[(A, B), (B, C), (X,Y)]
    输出:[(A, B, C), (X, Y)]
    

    即归并有相同元素的集合。

    有没有现成的库?

    或者自己实现的化思路是什么样的?

    第 1 条附言  ·  2019-03-13 17:03:04 +08:00
    为求表示简单,省略 set(),
    A,A 指代同一字符串,比如” UUID_A"
    13 条回复    2019-03-13 20:38:59 +08:00
    niknik
        1
    niknik  
       2019-03-13 16:41:04 +08:00
    楼下帮我回一下,我上个厕所👇
    shyrock
        2
    shyrock  
       2019-03-13 16:42:55 +08:00
    这不是元组列表吗。。。哪里有集合。。。
    bumz
        3
    bumz  
       2019-03-13 17:01:10 +08:00
    并查集?
    bumz
        4
    bumz  
       2019-03-13 17:01:26 +08:00
    @shyrock #2 逻辑上的集合
    ybbswc
        5
    ybbswc  
       2019-03-13 17:03:20 +08:00 via Android
    首先判断是否有相同元素,有的话就作并集。楼下来吧。(ーー;)
    bumz
        6
    bumz  
       2019-03-13 17:33:08 +08:00
    亲测并查集可行,复杂度 O(n),n 为输入中唯一元素的个数 * 每种元素平均出现次数

    https://gist.github.com/bumfo/26fc4865e27b48385ed650cd08fe6004
    bumz
        7
    bumz  
       2019-03-13 17:34:34 +08:00
    @bumz #6 想要 set 的话把 tuple 改成 set 一样
    bumz
        8
    bumz  
       2019-03-13 17:41:09 +08:00
    @bumz #6 复杂度 O(n log m),m 是不同元素的个数,n 是 m * 每个元素的平均出现次数
    bumz
        9
    bumz  
       2019-03-13 17:45:06 +08:00
    @ybbswc #5 这种做法复杂度 O(ab), a 是集合的个数,b 是每个集合中元素的个数的平均值
    lasuar
        10
    lasuar  
       2019-03-13 17:50:19 +08:00
    ```
    a = [(1,2), (2,3)]
    b = [(1,2)]

    print(set(a) | set(b))
    ```
    strict
        11
    strict  
       2019-03-13 18:36:38 +08:00
    复杂度目前想到的全是 m*n
    xor
        12
    xor  
       2019-03-13 20:28:01 +08:00 via iPhone
    @strict 并查集可以 n log m
    xor
        13
    xor  
       2019-03-13 20:38:59 +08:00 via iPhone
    @xor 并查集可以做到在现实中 O(m)
    严格来讲 O(m α(n)) 但是现实中 α(n) <= 4
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3412 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 11:32 · PVG 19:32 · LAX 03:32 · JFK 06:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.