题目形容

这是 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<Integer, List<Integer>> 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<Integer> list = map.get(key);            for (int i = 1; i < list.size(); i++) union(list.get(0), list.get(i));        }        return ans;    }    void add(Map<Integer, List<Integer>> map, int key, int val) {        List<Integer> list = map.getOrDefault(key, new ArrayList<>());        list.add(val);        map.put(key, list);    }}

TypeScript 代码：

const N = 20010const p: number[] = new Array<number>(N), sz = new Array<number>(N)let ans = 0function 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<number, Array<number>> = new Map<number, Array<number>>()    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<number, Array<number>>, key: number, val: number): void {    let list = map.get(key)    if (list == null) list = new Array<number>()    list.push(val)    map.set(key, list)}
  • 工夫复杂度：$O(n\sqrt{M})$
  • 空间复杂度：$O(n)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.952 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布