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

[goinghugh]

有个 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 有点像，但是他的是矩阵，我的是嵌套的结构。 求组大佬指点一二或者提醒一下类似的算法，我去借鉴一下解决思路，不用直接给我答案，谢谢~

[msg7086]

遍历数组，将每个 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]

union-find

[msg7086]

https://gist.github.com/msg7086/893a85964cc5735ae9525f5763e6ff74

[goinghugh]

@msg7086 十分感谢，没想到用字典，另外问句，这是什么语言？

[msg7086]

Ruby。

另外这里我想了很久，觉得还是用二级引用来做比较好，也就是 {key => (ref => array)} 这样的做法，这样替换数组只要把引用的 ref 对象里的数据换掉就行了，比 array.replace 和遍历字典分别替换都要方便些。

[8cbx]

并查集？？？

[layorlayor]

6L 说的对

[linxiaoziruo]

@msg7086 你这个算法的时间复杂度也是 O(n),n 是所有集合的元素个数。本质上还是线性遍历。我觉得楼主可能是要一个时间复杂度小于 O(n)的算法，也就是不要遍历。

[linxiaoziruo]

@8cbx 不是并查集。这个算法的核心问题在于怎么求交集，并查集的核心思想是解决连通图的问题。这是两个问题。

[fzy0728]

并查集没问题，本身就是存在连通关系。
感觉 1l 的存在一些问题
[
(1,2,3)

]

[fzy0728]

[
(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]

https://www.jianshu.com/p/def7767982ac

[linxiaoziruo]

@fzy0728 用并查集分组，然后合并是行不通的。关键就是并查集不能解决这个合并问题，想合并必须先求交集，想求交集就必须两个数组都遍历，假设有数组 A(m), B(n)，则合并一次的时间是 m*n。

[linxiaoziruo]

我觉得用 bitmap 可以解决这个问题。
对于 A，B 两个数组，用 BitMap 来存储，比如：
A：001011010101011100000010...
B：010101101100010110101110...
然后用 A&B，再求出结果中 1 的个数即可。这样既保证了空间高效，也保证了时间高效。

[aijam]

https://www.v2ex.com/t/516965#r_6593822

[shidenggui]

https://gist.github.com/shidenggui/933213ff4d1abfa142923ed766544112

用 union-find 写了下，感觉并不是最优的。

[layorlayor]

对于一个数字，找出他在哪些集合出现过，再用并查集把这些集合合并。

[frazy]

每个元素遍历，每个元素索引，如果同一 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]

我的错了

[nlzy]

https://gist.github.com/Nlzy/ed36a581b908a9f0503d33767504a8e3