这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos
输入：nums = [4,6,15,35]
输出：4
输入：nums = [20,50,9,63]
输出：2
输入：nums = [2,3,6,7,4,12,21,39]
输出：8
// 并查集的数组， 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;
/**
* 带压缩的并查集查找(即寻找指定数字的根节点)
* @param i
*/
private int find(int i) {
// 如果执向的是自己，那就是根节点了
if(fathers[i]==i) {
return i;
}
// 用递归的方式寻找，并且将整个路径上所有长辈节点的父节点都改成根节点，
// 例如1的父节点是2，2的父节点是3，3的父节点是4，4就是根节点，在这次查找后，1的父节点变成了4，2的父节点也变成了4，3的父节点还是4
fathers[i] = find(fathers[i]);
return fathers[i];
}
/**
* 并查集合并，合并后，child会成为parent的子节点
* @param parent
* @param child
*/
private void union(int parent, int child) {
int parentRoot = find(parent);
int childRoot = find(child);
// 如果有共同根节点，就提前返回
if (parentRoot==childRoot) {
return;
}
// child元素根节点是childRoot，现在将childRoot的父节点从它自己改成了parentRoot，
// 这就相当于child所在的整棵树都拿给parent的根节点做子树了
fathers[childRoot] = fathers[parentRoot];
// 合并后，这个树变大了，新增元素的数量等于被合并的字数元素数量
rootSetSize[parentRoot] += rootSetSize[childRoot];
// 更像最大数量
maxRootSetSize = Math.max(maxRootSetSize, rootSetSize[parentRoot]);
}
// 对数组中的每个数，算出所有质因数，构建map
for (int i=0;i<nums.length;i++) {
int cur = nums[i];
for (int j=2;j*j<=cur;j++) {
// 从2开始逐个增加，能整除的一定是质数
if(cur%j==0) {
map.computeIfAbsent(j, key -> new ArrayList<>()).add(nums[i]);
}
// 从cur中将j的因数全部去掉
while (cur%j==0) {
cur /= j;
}
}
// 能走到这里，cur一定是个质数，
// 因为nums[i]被除过多次后结果是cur，所以nums[i]能被cur整除，所以cur是nums[i]的质因数，应该放入map中
if (cur!=1) {
map.computeIfAbsent(cur, key -> new ArrayList<>()).add(nums[i]);
}
}
class Solution {
// 并查集的数组， 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;
/**
* 带压缩的并查集查找(即寻找指定数字的根节点)
* @param i
*/
private int find(int i) {
// 如果执向的是自己，那就是根节点了
if(fathers[i]==i) {
return i;
}
// 用递归的方式寻找，并且将整个路径上所有长辈节点的父节点都改成根节点，
// 例如1的父节点是2，2的父节点是3，3的父节点是4，4就是根节点，在这次查找后，1的父节点变成了4，2的父节点也变成了4，3的父节点还是4
fathers[i] = find(fathers[i]);
return fathers[i];
}
/**
* 并查集合并，合并后，child会成为parent的子节点
* @param parent
* @param child
*/
private void union(int parent, int child) {
int parentRoot = find(parent);
int childRoot = find(child);
// 如果有共同根节点，就提前返回
if (parentRoot==childRoot) {
return;
}
// child元素根节点是childRoot，现在将childRoot的父节点从它自己改成了parentRoot，
// 这就相当于child所在的整棵树都拿给parent的根节点做子树了
fathers[childRoot] = fathers[parentRoot];
// 合并后，这个树变大了，新增元素的数量等于被合并的字数元素数量
rootSetSize[parentRoot] += rootSetSize[childRoot];
// 更像最大数量
maxRootSetSize = Math.max(maxRootSetSize, rootSetSize[parentRoot]);
}
public int largestComponentSize(int[] nums) {
// 对数组中的每个数，算出所有质因数，构建map
for (int i=0;i<nums.length;i++) {
int cur = nums[i];
for (int j=2;j*j<=cur;j++) {
// 从2开始逐个增加，能整除的一定是质数
if(cur%j==0) {
map.computeIfAbsent(j, key -> new ArrayList<>()).add(nums[i]);
}
// 从cur中将j的因数全部去掉
while (cur%j==0) {
cur /= j;
}
}
// 能走到这里，cur一定是个质数，
// 因为nums[i]被除过多次后结果是cur，所以nums[i]能被cur整除，所以cur是nums[i]的质因数，应该放入map中
if (cur!=1) {
map.computeIfAbsent(cur, key -> new ArrayList<>()).add(nums[i]);
}
}
// 至此，map已经准备好了，接下来是并查集的事情，先要初始化数组
for(int i=0;i< fathers.length;i++) {
// 这就表示：数字i的父节点是自己
fathers[i] = i;
// 这就表示：数字i加上其下所有子节点的数量等于1（因为每个节点父节点都是自己，所以每个节点都没有子节点）
rootSetSize[i] = 1;
}
// 遍历map
for (int key : map.keySet()) {
// 每个key都是一个质因数
// 每个value都是这个质因数对应的数字
List<Integer> list = map.get(key);
// 超过1个元素才有必要合并
if (null!=list && list.size()>1) {
// 取第0个元素作为父节点
int parent = list.get(0);
// 将其他节点全部作为地0个元素的子节点
for(int i=1;i<list.size();i++) {
union(parent, list.get(i));
}
}
}
return maxRootSetSize;
}
}
个人在做这道题的时候，最大的误解就是对并查集合并的理解错误，导致做错，这里列出来，以避免您犯相同错误
以4,6,15,35这四个数字为例，以2为质因数的有4和6，以3为质因数的有6和15，以5为质因数的有15和35，以7为质因数的有35，逻辑关系如下图
所以，我们在说并查集合并操作，到底在合并什么？（这是核心，理解正确，这道题就解开了）
之前的误解如下图，以为是将红色箭头指向的四个集合合并，这样就达到了连通效果，实际上这样的理解是大错特错
接下来是自我救赎的纠正之路
首先，图就是错误的，既然是并查集，就应该按照并查集的数据结构来画图：一个int数组，数组下标就代表具体数字，值代表该数字的父节点是谁，例如 a[2]=5，其含义就是数字2的父节点是5，这是基本定义
并查集初始化的时候，每个元素的父节点都是它自己，如下图，注意，这个数组的长度其实是36（既从0到35），但是其他元素都用不上，所以我们无需关注它们，也就没有画进图中
接下来就是本题最核心的操作：合并，究竟该怎么合并呢？
答案是：相同质因数的数字合并，也就是说：以2为质因数的是4和6，所以4和6合并，以3为质因数的是6和15，所以6和15合并，以5为质因数的是15和35，所以15和35合并，7的质因数只有35，那就没法合并了
以上就是合并的操作，没错，就是这么简单：在并查集中对拥有相同质因数的数字进行合并
看到这里，您应该会疑惑：这样的合并，和连通有什么关系？和解题又有什么关系呢？
不急，咱能就用上面的数组，合并一下试试，稍后就会见证奇迹，也许能帮您找到豁然开朗的感觉
为了形象的理解，接下来我给数组再配上图，用来更形象的表达元素之间的父子关系，合并前的数组和关系图如下图，每个圆圈都有个箭头指向自己，表示每个元素的父节点是自己
接下来，合并4和6，这里的做法是把4作为6的父节点，所以，如下图，数组下标为4的元素值等于6，用逻辑图来表示，就是6的箭头指向4
接下来该合并6和15了，它们都有质因数3，这一步非常关键，因为我就是在这一步恍然大悟的，如下图，将6的父节点设置为4，再看逻辑关系图，明明只是在合并6和15，然而，4、6、15已经连通了！
恍然大悟：我们无需对各个质因数之间做什么，只要将每个质因数对应的数字合并即可，有的数字本来就属于多个质因数，所有跨质因数的连接都是因为这个特点而存在！
接下来是连接15和35，相信聪明的您也已经彻底领悟了，此时4个元素已经连通了
最后质因数7对应的数字只有35，一个数字就不需要合并操作了