欢迎访问我的GitHub
这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos
题目描述
- 难度：困难
- 编程语言：Java
- 给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：
- 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
- 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
- 返回图中最大连通组件的大小
- 示例 1：
输入：nums = [4,6,15,35]
输出：4
- 示例 2：
输入：nums = [20,50,9,63]
输出：2
- 示例 3：
输入：nums = [2,3,6,7,4,12,21,39]
输出：8
- 提示：
- 1 <= nums.length <= 2 * 104
- 1 <= nums[i] <= 105
- nums 中所有值都 不同
审题
- 可能是自身天资愚钝，欣宸第一时间居然没有搞懂题目中连通组件的大小的含义，以示例一为例，如下图，明明是三个边，为啥答案是4？
- 好吧，晕晕乎乎的想了半天终于搞清楚了：
- 不是让你数有几条边！
- 是让你数能够连在一起的元素，最多有几个？
- 如下图，有四个连在一起，答案就是4
- 如下图，50和9之间没有公因数，所以连不起来，导致四个数字中，20和50相连，9和63相连，那么，能连在一起的两个组合中，每个组合的数量都是2，答案就是2
- 磕磕绊绊终于读懂了题，再来看看解题前对知识储备的要求
需要哪些基本功？
- 请先掌握下面两个基本功，然后再能愉快的解题和优化，享受AC的喜悦，以及超过人数百分比提升的成就感
- 计算素数（埃氏筛选或者欧拉筛选，我这里用的是欧拉筛选）
- 并查集，需掌握以下技术点：
- 数据结构是数组，下标代表数字，值代表父节点是谁
- 查找（查找时顺便优化路径）
- 合并
- 上述基本功相信难不倒聪明的您，半小时内就能掌握，接下来，在欣宸图文并茂的解说中，一起享受解hard题的快乐吧
题目中还有哪些重要信息？
- 除了基本命题，还有三个至关重要的信息需要重点关注，他们是解题的关键，如下图，请记住这三个信息，很快就会用到
- 至此，准备工作已经完成，可以开始分析解题思路了，图文并茂的分析中，可能会让您产生一个错觉：hard题，就这？
解题思路
- 先画个图来描述完整流程
- 上面这个图，一开始可能您会看得有点晕乎，HashMap到底存了啥？并查集合并又合并了啥？
- 看不明白没事，真的没事，此图其实是解题思路的提前小结，接下来咱们用实际数字来演示解题思路，总之，就是要以最简单和具体的手段让您理解思路
实例解题演示解题思路
- 注意，接下来还是分析思路，暂时不涉及代码
- 以官方的示例来演示解题过程吧，假设输入数组有四个数字：4、6、15、35
- 首先，计算出每个数字的质因数，如下图，4的质因数是2，6的质因数是2和3，应该很好理解
- 接下来，根据上面的计算结果，新建一个HashMap，key是质因数，value是原数字，以2为例，它是4和6的质因数，所以，key就是2，value是个ArrayList，里面的内容是4和6，也就是说，根据上面的图得出下面的图
- 现在新建一个并查集，由于数字大小范围是从1到100000，所以，为了用数组下标表示数字，组数的大小就是100001，如此一来，array[100000]=123的意思就是：100000这个数字的父节点是123，这就是并查集概念中的数组定义的标准含义了
- 注意，数组创建后，每个元素值都是0，如下图
- 在本题中，咱们只关心4、6、15、35这四个数字，所以接下来画图的时候，数组中其他数字就不画上去了，后面的分析中，数组画出来就是下图的效果，相信您可以理解
- 按照并查集的定义，最初的时候，每个元素的父节点是它自己，所以给数组中每个元素赋值，值就等于数组下标，如下图所示，注意下图新增了辅助理解的逻辑图，这个是用来帮助大家理解每个节点和父节点关系的，可以看到每个节点的箭头指向自己，表示自己是自己的父节点（或者说每个元素都是根节点）
- 接下来，遍历前面准备好的HashMap，每个key对应的都是一个List，将这个list中的所有元素在并查集中合并，以key等于2为例，value中有两个数字：4和6，所以，在并查集中将4和6合并
- 第一个key是2，value中的数字是4和6，将4和6合并的效果如下图，红色是改过的地方，值等于4，表示数字6的父节点改成了4，为了便于理解，逻辑图也同步改动了，6指向自己的父节点4
- 第二个key是3，value中的数字是6和15，将6和15合并的效果如下图，蓝色是改过的地方，值等于6，表示数字15的父节点改成了6，为了便于理解，逻辑图也同步改动了，15指向自己的父节点6（逻辑图上可见，尽管只改了15的父节点，然而4，6，15已经在同一个树下了）
- 第三个key是5，value中的数字是15和35，将15和15合并的效果如下图，绿色是改过的地方，值等于15，表示数字35的父节点改成了15，为了便于理解，逻辑图也同步改动了，35指向自己的父节点15
- 至于第四个key，即7，它的value中只有一个数字35，谈不上合并，所以不做任何操作
- 至此，并查集合并操作完成，纵观整个并查树，虽然有多个树，唯有以4为根节点的树，其元素最多，有四个，所以，此题返回值就是4，连通的四个元素是4-6-15-35
- 画图画到手抽筋，相信您对解题思路已经完全掌握，接下来，开始编码吧
编码
- 接下来的编码，先将几个关键点逐个列举，然后再给出完整代码，并且会附上详细的注解，相信您可以轻松读懂
- 首先看看要定义哪些成员变量，如下，map是最重要的，刚才咱们详细分析过，代码注解也说得很细致了，然后是fathers、rootSetSize、maxRootSetSize都是并查集相关的数据结构
// 并查集的数组， fathers[3]=1的意思是：数字3的父节点是1
int[] fathers = new int[100001];
// 并查集中，每个数字与其子节点的元素数量总和，rootSetSize[5]=10的意思是：数字5与其所有子节点加在一起，一共有10个元素
int[] rootSetSize = new int[100001];
// map的key是质因数，value是以此key作为质因数的数字
// 例如题目的数组是[4,6,15,35]，对应的map就有四个key：2,3,5,7
// key等于2时，value是[4,6]，因为4和6的质因数都有2
// key等于3时，value是[6,15]，因为6和16的质因数都有3
// key等于5时，value是[15,35]，因为15和35的质因数都有5
// key等于7时，value是[35]，因为35的质因数有7
Map<Integer, List<Integer>> map = new HashMap<>();
// 用来保存并查集中，最大树的元素数量
int maxRootSetSize = 1;
- 并查集的查找根节点的操作也要注意，在查找过程中，将每个元素的父节点都改成了根节点，这