题目大意：
按公因数计算最大组件大小
给定一个由不同正整数的组成的非空数组 A，考虑下面的图：
- 有
A.length个节点，按从A[0]到A[A.length - 1]标记； - 只有当
A[i]和A[j]共用一个大于 1 的公因数时，A[i]和A[j]之间才有一条边。
返回图中最大连通组件的大小。
示例 1：
输入：[4,6,15,35] 输出：4
示例 2：
输入：[20,50,9,63] 输出：2
示例 3：
输入：[2,3,6,7,4,12,21,39] 输出：8
提示：
1 <= A.length <= 200001 <= A[i] <= 100000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=952
算法分析：
要想完全搞定这道题，首先必须要了解一下什么是并查集(Union-Find)。这里我尽量用些通俗易懂的语言跟大家分析明白，正好自己也能复习一遍。
Union-Find算法主要解决的就是路径问题。将相连的节点通过Union方法结合，另外通过Find方法确定两个节点是否相连。大致的思路就是，我们将需要连接的节点设置上相同的根，然后再看任意两个节点是否存在相同的根即可得知其是否相连。
举个例子来看，比如我们有五个节点分别叫做0，1，2，3，4。我们利用一个表(数组)来管理这些节点的根。在没有结合前，每个节点的根就是它们自己的index。
int[] roots = {0, 1, 2, 3, 4};如果我们想将节点1和3结合，那么我们可以将节点3的根修改为1的根。（根据喜好，将1的根修改为3同样可以），所以数组roots就变成：
int[] roots = {0, 1, 2, 1, 4};继续将节点0和2结合：
int[] roots = {0, 1, 0, 1, 4};再将节点0和3结合：这时需要注意一下，因为是更改根的值，3的根是节点1，所以要将节点1的值变为0
// 将3的根变为0的根
int[] roots = {0, 0, 0, 1, 4};
// 或者也可以是将0的根变为3的根
int[] roots = {1, 1, 0, 1, 4};所以结合方法可以写成：
void union(int i, int j) {
int rooti = root(i); // 取得节点i的根节点
int rootj = root(j); // 取得节点j的根节点
roots[rooti] = rootj; // roots[rootj] = rooti;也可以
}这时，实际上除了节点4之外，其他的4个节点1，2，3，4都是可以连通的。那么如何能判断他们是否联通呢？上文已经说过，只要他们拥有同一个根，那么就可以判定其是关联的。求根的方法很简单，只要看当前节点的值是否等于其index即可，如果不等，就是用当前的值作为index继续查找下去，直到相同为止。
// 查找根的方法
int root(int i) {
while (roots[i] != i) {
i = roots[i];
}
return i;
}
// int[] roots = {0, 0, 0, 1, 4};
// 例如节点4
// root[4] = 1, 4 != 1, 将index变为节点4的值也就是1
// root[1] = 0, 1 != 0, 将index变为节点1的值也就是0
// root[0] = 0, 0 == 0, 所以节点4的根是节点0最后就是find方法，也就是判断两个节点是否相连：
boolean find(int i, int j) {
return root(i) == root(j);
}至此，并查集(Union-Find)的基本思路就分析完了，那么如何运用到我们这道题中来呢？本题给出了一个int数组，任意两个数相连接的条件是看其是否存在大于1的公约数(也叫公因数)，那么我们可以将能够被某个公约数整除的数字都罗列出来，再将其union到一起，最后找出集合最大的那个即可。举例说明一下。比如：
int A[] = {2, 6, 9};那么，能被2的约数有2，6的约数有2, 3和6，9的约数则有3和9，即：
// 约数 -> 数组A中能被该约数整除的数
2 -> {2, 6}
3 -> {6, 9}
6 -> {6}
9 -> {9}我们按照Union-Find的思路先建立一个roots数组，因为A有三个元素，所以roots的长度也是3， 即：
int A[] = {2, 6, 9};
int roots[] = {0, 1, 2}同一约数包含的数字集合肯定存在公约数，所以该集合都可以Union，我们先看约数2包含的集合是2和6，也就是index为0和1的两个元素，我们将其合并：
int A[] = {2, 6, 9};
int roots[] = {0, 0, 2}继续看约数3包含的集合，其中有6和9，我们将其合并，因为6也同时出现在了约数2的集合中，所以，合并6和9的同时，数字2也同时与其变为同一根。
int A[] = {2, 6, 9};
int roots[] = {0, 0, 0} // 同样可合并为{2, 0, 2}之后的集合由于只包含一个数字，所以无需合并了。
所有的Union操作结束之后，我们可以遍历整个roots数组，算出所有节点的根，拥有子节点最多的根的所有节点数就是题目的结果。
最后看看完整的代码：
int[] roots; // Union-find要用到的数组
public int largestComponentSize(int[] A) {
// A数组长度
int length = A.length;
// 初始化roots数组
roots = new int[length];
for (int index = 0; index < length; index++) {
// 每个元素的根都设置为其自身在A中的index
roots[index] = index;
}
// 用于存储每个约数对应的可以被该约数整除的A中元素的inedx
Map<Integer, Set<Integer>> factorMap = new HashMap<>();
// 遍历A中所有数字
for (int index = 0; index < length; index++) {
int a = A[index];
// 因为A中每个数字最大为10万，遍历次数太多，所以在此做开方处理
// 这一步非常关键，如果不做这个处理，代码执行时间会大幅增加
// 不明白的，先别着急，继续向下看代码，文章最后会有详细的分析
int upper = (int) Math.sqrt(a);
// 因为数字a本身也是其约数，所以先将a的index加入到集合中
Set<Integer> indexSet0 = factorMap.getOrDefault(a, new HashSet<>());
indexSet0.add(index);
factorMap.put(a, indexSet0);
// 从2循环至upper，看哪些数字可以被a整除
for (int factor = 2; factor <= upper; factor++) {
// 如果可以整除
if (a % factor == 0) {
// 将a的index添加到该约数对应的集合中
Set<Integer> indexSet = factorMap.getOrDefault(factor, new HashSet<>());
indexSet.add(index);
factorMap.put(factor, indexSet);
// 将该约数除干净，到不能整除为止
while (a % factor == 0) {
a = a / factor;
// 如果除法结果不为1，那么结果也是该数字的约数之一，
// 同样需要将a的index存入该约数对应的集合
if (a != 1) {
Set<Integer> indexSet2 = factorMap.getOrDefault(a, new HashSet<>());
indexSet2.add(index);
factorMap.put(a, indexSet2);
}
}
// 因为除了自身之外的约数一定小于等于其自身的一半，
// 为了减少循环次数，此处可以break
if (a < factor * 2) {
break;
}
}
}
}
// 所有约数对应的A中数字整理完之后，开始Union操作
for (Map.Entry<Integer, Set<Integer>> entrySet : factorMap.entrySet()) {
// 循环取出所有约数，对应的集合，因为他们存在同一约数，所以可以合并
Set<Integer> set = entrySet.getValue();
if (set.size() > 1) {
int i = -1;
// 先取出集合中的第一个数字
for (Integer seti : set) {
set.remove(seti);
i = seti;
break;
}
// 再将第一个数字与其他数字Union
for (Integer j : set) {
union(i, j);
}
}
}
// Union操作结束后，开始统计每个根拥有的节点数量
Map<Integer, Integer> rootCountMap = new HashMap<>();
for (int root : roots) {
// 当前节点的根拥有的全部节点数量。
int count = rootCountMap.getOrDefault(root(root), 0);
// 将当前节点算入其数量中（节点数加一）
rootCountMap.put(root(root), count + 1);
}
// 统计完每个根拥有的节点数量后，找出数量最大的即是结果
int res = 0;
for (Map.Entry<Integer, Integer> entrySet : rootCountMap.entrySet()) {
res = Math.max(res, entrySet.getValue());
}
return res;
}
int root(int i) {
while (roots[i] != i) {
i = roots[i];
}
return i;
}
void union(int i, int j) {
int rooti = root(i);
int rootj = root(j);
roots[rooti] = rootj;
}总结：
其实本题的解法并没有用到find方法，因为union之后就可以统计出结果了。另外本题的算法还可以再进行优化，比如边Union边统计等，由于时间原因，就不展开分析了。
最后再说说代码中提到的开方处理。简单来说，求一个数字所有约数的方法可以从1循环到其本身，可以被整除的都是它的约数。比如说36，我们从1循环到36，可以得到1，2，3，4，6，9，12，18，36这些质数。这需要循环36次。优化一下思路，其实除去数字本身之外的约数，一定是小于其自身一半的，其实循环18次再加上数字本身就可以。虽然对于当今高性能的计算机来说，循环18次和36次所用时间的差别几乎可以忽略不计，但是如果数字很大，比如36兆，那么，差别就会变得非常明显。
但这远远不是最优解，再优化一下我们的思路，来看看36的这些质数，除了1和36本身之外，其他的所有质数2，3，4，6，9，12，从两边到中间都是可以两两相乘等于36的，也就是说，当我们得到最小质数2的同时，也就知道了最大质数一定是18，这组质数的中点就是36的平方根6，所以，当我们知道了6之前的所有质数时，6之后的也都相应得出了，这就是为什么要开方的原因。当然不能以正数开方的数字同样适用这个规则。这一点，大家需要自己整理一下的逻辑。所以我们的时间复杂度可以从O(n)精简到O(sqrt(n))
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-952-largest-component-size-by-common-factor-白话算法分析/