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

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

给定一个由不同正整数的组成的非空数组 nums，考虑下面的图：

• 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记
• 只有当 nums[i] 和 nums[j] 共有一个大于 1 的公因数时，才将两个节点相连

返回图中最大连接组件的大小。

示例 1:

输入：nums = [4,2,12,6,14,10,9]
输出：3

提示:

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 10^5

解析

使用并查集，将每个数与其所有质因数合并，最后统计每个连通分量的大小。

var largestComponentSize = function (nums) {
  const max = Math.max(...nums);
  const parent = Array.from({ length: max + 1 }, (_, i) => i);

  const find = (x) => {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  };

  const union = (x, y) => {
    const px = find(x);
    const py = find(y);
    if (px !== py) parent[px] = py;
  };

  const getPrimeFactors = (num) => {
    const factors = new Set();
    let x = num;
    for (let i = 2; i * i <= x; i++) {
      if (x % i === 0) {
        factors.add(i);
        while (x % i === 0) x /= i;
      }
    }
    if (x > 1) factors.add(x);
    return factors;
  };

  const primeToIndex = new Map();
  for (const num of nums) {
    const factors = getPrimeFactors(num);
    for (const f of factors) {
      if (!primeToIndex.has(f)) {
        primeToIndex.set(f, num);
      } else {
        union(num, primeToIndex.get(f));
      }
    }
  }

  const count = new Map();
  for (const num of nums) {
    const root = find(num);
    count.set(root, (count.get(root) || 0) + 1);
  }

  return Math.max(...count.values());
};

时间复杂度 O(n * sqrt(max))，空间复杂度 O(max)。