REST

并查集

1. 并查集基本结构和操作
   1. 有若干个样本a、b、c、d…类型假设是V
   2. 在并查集中一开始认为每个样本都在单独的集合里
   3. 用户可以在任何时候调用如下两个方法：
      1. boolean isSameSet(V x, V y)：查询样本x和样本y是否属于一个集合
      2. void union(V x, V y)：把x和y各自所在集合的所有样本合并成一个集合
   4. isSameSet和union方法的代价越低越好，最好O(1)
2. 思路：isSameSet方法，我们首先设计为每个元素有一个指向自己的指针，成为代表点。
   1. 想要判断两个元素是否在一个集合中，分别调用这两个元素的向上指针，不断向上指
   2. 两个元素最上方的指针如果内存地址相同，那么两个元素在一个集合中，反之不在
3. 思路：union方法，例如将a所在的集合和e所在的集合合并成一个大的集合union(a,e)。
   1. a的代表点指针是a，e的代表点指针是e，我们拿较小的集合挂在大的集合下面.
   2. 比如e小，那么e放在a的下面。
   3. 链接的方式为小集合e头结点本来指向自己的代表节点，现在要指向a节点
4. 并查集的优化点主要有两个，两种优化的目的都是为了更少的遍历节点。
   1. 一个是合并的时候小的集合挂在大的集合下面，
   2. 第二个优化是找某节点最上方的代表节点，把沿途节点全部拍平(直接挂在代表节点之下)，下次再找该沿途节点，都变为O(1)。
   3. 由于我们加入了优化，如果N个节点，我们调用findFather越频繁，我们的时间复杂度越低，因为第一次调用我们加入了优化。
   4. 如果findFather调用接近N次或者远远超过N次，我们并查集的时间复杂度就是O(1)。
   5. 该复杂度只需要记住结论，证明无须掌握。该证明从1964年一直研究到1989年，整整25年才得出证明！算法导论23章，英文版接近50页的证明。

例题,多属性找人数

1. 题目解释:
   1. 如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人;
   2. 请合并users，返回合并之后的用户数量
   3. 学生实例有三个属性，身份证信息，B站ID,Github的Id。
   4. 我们认为，任何两个学生实例，只要身份证一样，或者B站ID一样，或者Github的Id一样，我们都算一个人。
   5. 给一大批学生实例，输出有实质有几个人？
2. 思路：
   1. 把实例的三个属性建立三张映射表，
   2. 每个实例去和前面的对比,如果出现过,就把两个数据表union桥联
   3. 三张表,桥联,每一个新样本到来,都看哪个字段能不能跟前面某一个桥联上,反正并查集会把该连的连到一块的
   4. 重复出现的字段只用保留第一个: 目的是把不连通的数字连通到一起,选谁都行,并查集内部都是连好的,最后看并查集里有几个集合就行了
   5. 因为并查集的只有代表点的sizeMap才有记录,看sizeMap多大就有几个人

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。