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

推荐学习书目

› 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

This topic created in 2645 days ago, the information mentioned may be changed or developed.

比如

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

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

有没有现成的库？

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

Supplement 1 · Mar 13, 2019

为求表示简单，省略 set()，
A，A 指代同一字符串，比如” UUID_A"

归并

集合

Python

现成

13 replies • 2019-03-13 20:38:59 +08:00

niknik

Mar 13, 2019

楼下帮我回一下，我上个厕所👇

shyrock

Mar 13, 2019

这不是元组列表吗。。。哪里有集合。。。

bumz

Mar 13, 2019

并查集？

bumz

Mar 13, 2019

@shyrock #2 逻辑上的集合

ybbswc

Mar 13, 2019 via Android

首先判断是否有相同元素，有的话就作并集。楼下来吧。(ーー;)

bumz

Mar 13, 2019

亲测并查集可行，复杂度 O(n)，n 为输入中唯一元素的个数 * 每种元素平均出现次数

https://gist.github.com/bumfo/26fc4865e27b48385ed650cd08fe6004

bumz

Mar 13, 2019

@bumz #6 想要 set 的话把 tuple 改成 set 一样

bumz

Mar 13, 2019

@bumz #6 复杂度 O(n log m)，m 是不同元素的个数，n 是 m * 每个元素的平均出现次数

bumz

Mar 13, 2019

@ybbswc #5 这种做法复杂度 O(ab), a 是集合的个数，b 是每个集合中元素的个数的平均值

freemoon

Mar 13, 2019

```
a = [(1,2), (2,3)]
b = [(1,2)]

print(set(a) | set(b))
```

strict

Mar 13, 2019

复杂度目前想到的全是 m*n

xor

Mar 13, 2019 via iPhone

@strict 并查集可以 n log m

xor

Mar 13, 2019 via iPhone

@xor 并查集可以做到在现实中 O(m)
严格来讲 O(m α(n)) 但是现实中 α(n) <= 4