算法面试高频题难度35，数学与并查集的结合

　　题目描述
　　这是LeetCode上的952。按公因数计算最大组件大小，难度为困难。
　　Tag：数学、并查集
　　给定一个由不同正整数的组成的非空数组nums，考虑下面的图：有nums。length个节点，按从nums〔0〕到nums〔nums。length1〕标记；只有当nums〔i〕和nums〔j〕共用一个大于111的公因数时，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
　　提示：1nums。length21041nums。length2imes1041nums。length21041nums〔i〕1051nums〔i〕1051nums〔i〕105nums中所有值都不同枚举质因数并查集
　　先考虑如何使用nums进行建图，nums大小为n2104n2imes104n2104，枚举所有点对并通过判断两数之间是否存在边的做法复杂度为O（n2M）O（n2sqrt｛M｝）O（n2M）（其中M1e5M1e5M1e5为nums〔i〕nums〔i〕nums〔i〕的最大值），无须考虑。
　　而不通过枚举点求公约数的建图方式，可以对nums〔i〕nums〔i〕nums〔i〕进行质因数分解（复杂度为O（nums〔i〕）O（sqrt｛nums〔i〕｝）O（nums〔i〕）），假设其分解出来的质因数集合为SSS，我们可以建立从SkS｛k｝Sk到nums〔i〕nums〔i〕nums〔i〕的映射关系，若nums〔i〕nums〔i〕nums〔i〕与nums〔j〕nums〔j〕nums〔j〕存在边，则nums〔i〕nums〔i〕nums〔i〕和nums〔j〕nums〔j〕nums〔j〕至少会被同一个质因数所映射。
　　维护连通块数量可以使用并查集来做，维护映射关系可以使用哈希表来做。
　　维护映射关系时，使用质因数为key，下标值iii为value（我们使用下标iii作为点编号，而不是使用nums〔i〕nums〔i〕nums〔i〕，是利用nums〔i〕nums〔i〕nums〔i〕各不相同，从而将并查集数组大小从1e51e51e5收窄到21042imes1042104）。
　　同时在使用并查集维护连通块时，同步维护每个连通块大小sz以及当前最大的连通块大小ans。
　　Java代码：classSolution｛staticintN20010；staticint〔〕pnewint〔N〕，sznewint〔N〕；intans1；intfind（intx）｛if（p〔x〕！x）p〔x〕find（p〔x〕）；returnp〔x〕；｝voidunion（inta，intb）｛if（find（a）find（b））sz〔find（a）〕sz〔find（b）〕；p〔find（b）〕p〔find（a）〕；ansMath。max（ans，sz〔find（a）〕）；｝publicintlargestComponentSize（int〔〕nums）｛intnnums。MapInteger，ListIntegermapnewHashMap（）；for（inti0；i）｛intcurnums〔i〕；for（intj2；j）｛if（curj0）add（map，j，i）；while（curj0）｝if（cur1）add（map，cur，i）；｝for（inti0；i）｛p〔i〕i；sz〔i〕1；｝for（intkey：map。keySet（））｛ListIntegerlistmap。get（key）；for（inti1；ilist。size（）；i）union（list。get（0），list。get（i））；｝｝voidadd（MapInteger，ListIntegermap，intkey，intval）｛ListIntegerlistmap。getOrDefault（key，newArrayList（））；list。add（val）；map。put（key，list）；｝｝
　　TypeScript代码：constN20010constp：number〔〕newArraynumber（N），sznewArraynumber（N）letans0functionfind（x：number）：number｛if（p〔x〕！x）p〔x〕find（p〔x〕）returnp〔x〕｝functionunion（a：number，b：number）：void｛if（find（a）find（b））returnsz〔find（a）〕sz〔find（b）〕p〔find（b）〕p〔find（a）〕ansMath。max（ans，sz〔find（a）〕）｝functionlargestComponentSize（nums：number〔〕）：number｛constnnums。lengthconstmap：Mapnumber，ArraynumbernewMapnumber，Arraynumber（）for（leti0；i）｛letcurnums〔i〕for（letj2；j）｛if（curj0）add（map，j，i）while（curj0）curj｝if（cur1）add（map，cur，i）｝for（leti0；i）｛p〔i〕i；sz〔i〕1｝ans1for（constkeyofmap。keys（））｛constlistmap。get（key）for（leti1；ilist。i）union（list〔0〕，list〔i〕）｝returnans｝；functionadd（map：Mapnumber，Arraynumber，key：number，val：number）：void｛letlistmap。get（key）if（listnull）listnewArraynumber（）list。push（val）map。set（key，list）｝时间复杂度：O（nM）O（nsqrt｛M｝）O（nM）空间复杂度：O（n）O（n）O（n）
　　链接：https：juejin。cnpost7214855127626104869