LC.P952[按公因数计算最大组件大小]

题目描述

给定一个由不同正整数的组成的非空数组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 * 104
  • 1 <= nums[i] <= 105
  • nums 中所有值都 不同

思路

由题意，如果$nums[i]$和$nums[j]$存在边，则至少会被同一个质因数所映射。

利用并查集维护联通块数量，用哈希表维护映射关系。

映射关系为：<质因数，下标$i$>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    int[] p;
    int[] size;

    private int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        size[px] += size[py];
        p[py] = p[px];
    }

    public int largestComponentSize(int[] nums) {
        int n = nums.length, ans = 1;
        p = new int[n];
        size = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            size[i] = 1;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int num = nums[i];
            for (int j = 2; j * j <= num; ++j) {
                if (num % j == 0) {
                    List<Integer> list = map.getOrDefault(j, new ArrayList<>());
                    list.add(i);
                    map.put(j, list);
                }
                while (num % j == 0) num /= j;
            }
            if (num > 1) {
                List<Integer> list = map.getOrDefault(num, new ArrayList<>());
                list.add(i);
                map.put(num, list);
            }
        }
        for (Integer key : map.keySet()) {
            List<Integer> list = map.get(key);
            for (int i = 1; i < list.size(); ++i) {
                union(list.get(0), list.get(i));
                ans = Math.max(ans, size[find(list.get(0))]);
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n\sqrt{m})$，$m$为$nums$数组中的最大值
  • 空间复杂度：$O(n)$