这是一个创建于 2152 天前的主题，其中的信息可能已经有所发展或是发生改变。
有个 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 有点像，但是他的是矩阵，我的是嵌套的结构。 求组大佬指点一二或者提醒一下类似的算法，我去借鉴一下解决思路，不用直接给我答案，谢谢~
 |
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} 一直跑完以后，把字典里的值对象去重就是结果了。 |
 |
2
leiuu 2019-01-31 12:07:45 +08:00 1
union-find
|
|
3
msg7086 2019-01-31 12:24:53 +08:00
|
|
5
msg7086 2019-01-31 12:58:57 +08:00
Ruby。
另外这里我想了很久，觉得还是用二级引用来做比较好，也就是 {key => (ref => array)} 这样的做法，这样替换数组只要把引用的 ref 对象里的数据换掉就行了，比 array.replace 和遍历字典分别替换都要方便些。 |
 |
6
8cbx 2019-01-31 13:05:00 +08:00
并查集？？？
|
 |
7
layorlayor 2019-01-31 14:00:54 +08:00
6L 说的对
|
 |
8
linxiaoziruo 2019-01-31 14:19:43 +08:00
@msg7086 你这个算法的时间复杂度也是 O(n),n 是所有集合的元素个数。本质上还是线性遍历。我觉得楼主可能是要一个时间复杂度小于 O(n)的算法，也就是不要遍历。
|
|
9
linxiaoziruo 2019-01-31 14:23:55 +08:00
@8cbx 不是并查集。这个算法的核心问题在于怎么求交集，并查集的核心思想是解决连通图的问题。这是两个问题。
|
 |
10
fzy0728 2019-01-31 14:41:17 +08:00
并查集没问题，本身就是存在连通关系。
感觉 1l 的存在一些问题 [ (1,2,3) ] |
|
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 |
|
12
fzy0728 2019-01-31 14:52:40 +08:00
|
|
13
linxiaoziruo 2019-01-31 14:52:40 +08:00
@fzy0728 用并查集分组，然后合并是行不通的。关键就是并查集不能解决这个合并问题，想合并必须先求交集，想求交集就必须两个数组都遍历，假设有数组 A(m), B(n)，则合并一次的时间是 m*n。
|
|
14
linxiaoziruo 2019-01-31 14:54:22 +08:00
我觉得用 bitmap 可以解决这个问题。
对于 A，B 两个数组，用 BitMap 来存储，比如： A：001011010101011100000010... B：010101101100010110101110... 然后用 A&B，再求出结果中 1 的个数即可。这样既保证了空间高效，也保证了时间高效。 |
 |
15
aijam 2019-01-31 14:54:43 +08:00
|
 |
16
shidenggui 2019-01-31 15:00:52 +08:00
|
|
17
layorlayor 2019-01-31 15:01:47 +08:00
对于一个数字，找出他在哪些集合出现过，再用并查集把这些集合合并。
|
 |
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); |
|
19
frazy 2019-01-31 15:31:55 +08:00
我的错了
|
 |
20
nlzy 2019-01-31 15:47:37 +08:00
|
 |
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} ] 吗 |
 |
22
hitmanx 2019-01-31 18:23:00 +08:00
@linxiaoziruo
bitmap 如果碰到上限大就不好弄了，比如元素最大可以是 U32 甚至 U64 ；另外生成 bitmap 也需要 O(n)，n 为全部元素数量（我感觉不可能有低于 O(n)的算法，因为最坏情况下至少所有元素都需要遍历一次） |
|
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 |
|
24
8cbx 2019-02-03 12:57:53 +08:00
感觉并查集完美解决了啊，初始化：每个元素的父是自己；然后对于每一组中的每一个元素，先判断自己是否已经有非自己的父，有则把这组的第一个元素和他的父并，否则把自己并到这组的第一个元素下面
|
Select Language