952. 按公因数计算最大组件大小 : 枚举质因数 + 并查集运用题后端

题目描述这是 LeetCode 上的 952. 按公因数计算最大组件大小，难度为困难。
Tag : 「数学」、「并查集」
给定一个由不同正整数的组成的非空数组 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 \times 10^4$
$1 <= nums[i] <= 10^5$
nums 中所有值都不同

枚举质因数 + 并查集先考虑如何使用 nums 进行建图，nums 大小为 $n = 2 \times 10^4$，枚举所有点对并通过判断两数之间是否存在边的做法复杂度为 $O(n^2\sqrt{M})$（其中 $M = 1e5$ 为 $nums[i]$ 的最大值），无须考虑。
而不通过「枚举点 + 求公约数」的建图方式，可以对 $nums[i]$ 进行质因数分解（复杂度为 $O(\sqrt{nums[i]})$），假设其分解出来的质因数集合为 $S$，我们可以建立从 $S_{k}$ 到 $nums[i]$ 的映射关系，若 $nums[i]$ 与 $nums[j]$ 存在边，则 $nums[i]$ 和 $nums[j]$ 至少会被同一个质因数所映射。
维护连通块数量可以使用「并查集」来做，维护映射关系可以使用「哈希表」来做。
维护映射关系时，使用质因数为 key，下标值 $i$ 为 value（我们使用下标 $i$ 作为点编号，而不是使用 $nums[i]$ ，是利用$nums[i]$ 各不相同，从而将并查集数组大小从 $1e5$ 收窄到 $2 \times 10^4$)。
同时在使用「并查集」维护连通块时，同步维护每个连通块大小 sz 以及当前最大的连通块大小 ans。
Java 代码：

class Solution { static int N = 20010; static int[] p = new int[N], sz = new int[N]; int ans = 1; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void union(int a, int b) { if (find(a) == find(b)) return ; sz[find(a)] += sz[find(b)]; p[find(b)] = p[find(a)]; ans = Math.max(ans, sz[find(a)]); } public int largestComponentSize(int[] nums) { int n = nums.length; Map> map = new HashMap<>(); for (int i = 0; i < n; i++) { int cur = nums[i]; for (int j = 2; j * j <= cur; j++) { if (cur % j == 0) add(map, j, i); while (cur % j == 0) cur /= j; } if (cur > 1) add(map, cur, i); } for (int i = 0; i <= n; i++) { p[i] = i; sz[i] = 1; } for (int key : map.keySet()) { List list = map.get(key); for (int i = 1; i < list.size(); i++) union(list.get(0), list.get(i)); } return ans; } void add(Map> map, int key, int val) { List list = map.getOrDefault(key, new ArrayList<>()); list.add(val); map.put(key, list); } }

TypeScript 代码：

const N = 20010 const p: number[] = new Array(N), sz = new Array(N) let ans = 0 function find(x: number): number { if (p[x] != x) p[x] = find(p[x]) return p[x] } function union(a: number, b: number): void { if (find(a) == find(b)) return sz[find(a)] += sz[find(b)] p[find(b)] = p[find(a)] ans = Math.max(ans, sz[find(a)]) } function largestComponentSize(nums: number[]): number { const n = nums.length const map: Map> = new Map>() for (let i = 0; i < n; i++) { let cur = nums[i] for (let j = 2; j * j <= cur; j++) { if (cur % j == 0) add(map, j, i) while (cur % j == 0) cur /= j } if (cur > 1) add(map, cur, i) } for (let i = 0; i < n; i++) { p[i] = i; sz[i] = 1 } ans = 1 for (const key of map.keys()) { const list = map.get(key) for (let i = 1; i < list.length; i++) union(list[0], list[i]) } return ans }; function add(map: Map>, key: number, val: number): void { let list = map.get(key) if (list == null) list = new Array() list.push(val) map.set(key, list) }

时间复杂度：$O(n\sqrt{M})$
空间复杂度：$O(n)$

最后这是我们「刷穿 LeetCode」系列文章的第 No.952 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSou... 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地
【952. 按公因数计算最大组件大小 : 枚举质因数 + 并查集运用题】本文由mdnice多平台发布