递归并查集,轻松权重优化。"/>
[L氏并查集] Python 列表法实现非递归并查集,轻松权重优化。
一般的并查集都是用递归或者新建一个类来实现,这里介绍一种用Python来实现的非递归非函数并查集,这个方法暂时未在其他地方见过,尤其是中文领域目前还未见过,很可能是搜索引擎无法搜索到正确内容的原因,所以不排除会有撞车的,不过在撞车警告之前,我都视为是我原创,LeetCode中文版上并查集的题目我基本都写了两种解,在那些题的题解里应该可以看到。(20190730)
假设存在n个点存在连通关系connections :
n = 6, connections = [[0, 1], [0, 2], [4, 3], [1, 2], [3, 2]]
求两个点的连通性,就可以使用并查集去检验:
def LsUnionFindSet(self, n: int, connections: List[str], a: int, b: int) -> bool:p = [[i] for i in range(n)] #并查集初始化for x, y in connections: #遍历边if p[x] is not p[y]: #如果两个列表指针不相等p[x].extend(p[y]) #将y列表并进x列表for z in p[y]: #遍历y列表的元素p[z] = p[x] #所有y列表的元素都指向x集合return p[a] == p[b]
[a, b] 为[0, 4],返回为True
[a, b] 为[2, 5],返回为False
时间复杂度应该和常规的并查集一致,每次赋值其实都是指针赋值,相对来说计算量并不大,z层的总循环在我个人多次计数试验应该是在~这样,符合并查集时间复杂度即阿克曼反函数,具体证明应参考并查集的标准证明,空间复杂度,传递过程大多是传递集合的指针地址,并不增加额外空间。
算上临时空间,最大空间为,即所有元素均分成2块,合并过程中会产生的临时空间,但合并结束后,临时空间将会被销毁。
同时,这种方法非常容易进行权重优化:
def LsUnionFindSet(self, n: int, connections: List[str], a: int, b: int) -> bool:p = [[i] for i in range(n)] #并查集初始化for x, y in connections: #遍历边if p[x] is not p[y]: #如果两个列表指针不相等if len(p[x]) < len(p[y]) #如果x所在的集合小于y所在的集合x, y = y, x #交换x,y使得优先使小集合并入大集合p[x].extend(p[y]) #将y列表并进x列表for z in p[y]: #遍历y列表的元素p[z] = p[x] #所有y列表的元素都指向x集合return p[a] == p[b]
只需要一个判断就可以让复杂度稳定在以下了,leetcode上用这种方法可以很轻松拿到95-100%的时间成绩。
此方法除了rust,大多数语言都可以轻松实现,无指针语言如java/javascript的代码结构基本跟python一致,有指针的语言如c++/golang等则需要单独处理指针引用,指针安全语言rust则需要包裹智能指针,相对比较麻烦。
下面是静态语言go的链表版实现样例
// 链表
type ListNode struct {Val intNext *ListNode
}// 并查集结构,只需要记录链表头尾和大小
type UnionFindSet struct {head *ListNodetail *ListNodesize int
}func LsUnionFindSet(n int, connections [][]int) {p := make([]*UnionSet, n) // 并查集初始化for i := range p {node := &ListNode{i, nil}p[i] = &UnionFindSet {head: node,tail: node,size: 1,}}for _, c := range connections {x, y := c[0], c[1]if p[x] != p[y] {if p[x].size < p[y].size { // 比较两个并查集尺寸并进行权重优化,O(1)x, y = y, x}p[x].tail.Next = p[y].head // 大集合的链表尾部连上小集合的链表头部,O(1)p[x].tail = p[y].tail // 更新大集合的链表尾部,O(1)p[x].size += p[y].size // 更新大集合的尺寸,O(1)for z := p[y].head; z != nil; z = z.Next {p[z.Val] = p[x] // 遍历小集合,把小集合里所有坐标的集合指向改成大集合} // O(min(p[x].size, p[y].size))} }
}
更多推荐
[L氏并查集] Python 列表法实现非递归并查集,轻松权重优化。
发布评论