952. 按公因数计算最大组件大小

Problem: 952. 按公因数计算最大组件大小

思路

这个问题可以通过并查集来解决。我们可以将每个数的因子看作是连接这些数的桥梁。如果两个数有共同的因子，那么这两个数就可以被归为同一组。我们的目标是找到最大的这样的组。

解题方法

首先，我们需要初始化并查集。然后，对于数组中的每个数，我们找出它的所有因子，并将这些因子对应的数进行合并。最后，我们找出并查集中最大的集合。

复杂度

时间复杂度:

$O(n\sqrt{m})$，其中$n$是数组的长度，$m$是数组中的最大值。这是因为我们需要对每个数找出其所有的因子，这个过程的时间复杂度是$O(\sqrt{m})$。

空间复杂度:

$O(n)$，我们需要使用额外的空间来存储并查集。

Code

class Solution {
    public static int MAXV=100001;
    public static int MAXN = 20001;
    public static int[] factors = new int[MAXV];
    public static int[] f = new int[MAXN];
    public static int[] size = new int[MAXN];
    public static int n;

    public static void build() {
        for (int i = 0; i < n; i++) {
            f[i] = i;
            size[i] = 1;
        }
        Arrays.fill(factors, -1);

    }

    public static int find(int i) {
        if (i != f[i]) {
            f[i] = find(f[i]);
        }
        return f[i];

    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            f[fx] = fy;
            size[fy] += size[fx];
        }

    }

    public static int maxSize() {
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans = Math.max(ans, size[i]);
        }
        return ans;
    }

    public static int largestComponentSize(int[] nums) {
        n = nums.length;
        build();
        for (int i = 0, x; i < n; i++) {
            x = nums[i];
            for (int j = 2; j <= x / j; j++) {
                if (x % j == 0) {
                    if (factors[j] == -1) {
                        factors[j] = i;
                    } else {
                        union(factors[j], i);
                    }
                    while (x % j == 0) {
                        x /= j;
                    }
                }
            }
            if (x > 1) {
                if (factors[x] == -1) {
                    factors[x] = i;
                } else {
                    union(factors[x], i);
                }
            }
        }

        return maxSize();

    }
}