算法leetcode

力扣952-按公因数计算最大组件大小

字数统计: 1.1k字   |   阅读时长: 4分
, ,

摘要: 本文详细拆解 力扣952-按公因数计算最大组件大小。分解质因数+并查集

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来看一个数论与并查集结合的问题，综合性比较强。

$1 题目

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

  • 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
  • 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。

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

提示：

1
2
3
1 <= nums.length <= 2 * 1e4
1 <= nums[i] <= 1e5
nums 中所有值都 不同

示例 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

$2 题解

算法：素数筛 + 带权并查集

用带权并查集维护 nums 中的所有节点。集合级的权值表示连通分量的节点个数。

对并查集中的点进行连边，使得有大于 1 的公因数的节点在同一个连通分量中。连边完成后，访问每个连通分量，返回最大的权值。

连边的过程最直接的方法是枚举所有的节点对，判断是否有公因数之后进行连边。但由于点的个数 N 很大，这种 $O(N^{2})$ 的枚举边的方式不可接受。

假设 nums 的最大值为 maxn，由于 nums 中的元素各不相同，可以将 [1, maxn] 范围内的数全部维护在带权并查集中，初始权值均为 0，

经过一系列连边之后，节点 i 的权值 _weight[i] 若为 0，表示 i 不在 nums 中，否则 _weight[i] 表示连通分量的节点个数，注意实际数据结构中的连在一起的节点个数可能大于 _weight[i]，其中权值为 0 的节点不计入联通分量的节点个数。这样维护的话，编程方便。

初始化带权并查集之后，在 [2, maxn] 的范围执行线性筛，每当筛到一个素数 i，枚举 [2i, maxn] 范围内 i 的倍数 j。

如果 i 在 nums 中，则将 i 的权置为 1；

如果 j 在 nums 中，则先将 j 的权置为 1，再 merge(i, j)，这里 i, j 的权值均有可能为 0，但在数据结构上仍将 i, j 合并。

代码 (C++)

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
class UnionFindSet
{
public:
    UnionFindSet(int n):n(n)
    {
        _rank = vector<int>(n, 0);
        _father = vector<int>(n, 0);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
        _weight = vector<int>(n, 0);
    }

    bool same(int a, int b)
    {
        return _find(a) == _find(b);
    }

    void merge(int a, int b)
    {
        // a 是目标数字，b 是质数
        int x = _find(a);
        int y = _find(b);
        if(x == y) return;

        if(_rank[x] > _rank[y])
        {
            _father[y] = x;
            _weight[x] += _weight[y];
        }
        else
        {
            _father[x] = y;
            _weight[y] += _weight[x];
            if(_rank[x] == _rank[y])
                ++_rank[y];
        }
    }

    void change_weight(int x)
    {
        _weight[x] = 1;
    }

    int stat()
    {
        int result = 0;
        for(int i = 0; i < n; ++i)
        {
            if(_father[i] == i)
                result = max(result, _weight[i]);
        }
        return result;
    }

private:
    vector<int> _rank;
    vector<int> _father;
    vector<int> _weight; // 连通分量大小
    int n;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        _father[x] = _find(_father[x]);
        return _father[x];
    }
};

class Solution {
public:
    int largestComponentSize(vector<int>& A) {
        int N = *max_element(A.begin(), A.end());
        int n = A.size();
        nums = unordered_set<int>(A.begin(), A.end());
        UnionFindSet unionfindset(N + 1);
        primes_sieve(N + 1, &unionfindset);
        return unionfindset.stat();
    }

private:
    unordered_set<int> nums;

    void primes_sieve(int n, UnionFindSet* it) {
        if(n < 2) return;
        bool* vec = new bool[n];
        for(int i = 0; i < n; ++i)
            vec[i] = true;
        vec[0] = false;
        vec[1] = false;
        int cnt = 0;
        for(int i = 2; i < n; ++i)
        {
            if(vec[i])
            {
                if(nums.find(i) != nums.end())
                {
                    it -> change_weight(i);
                }
                for(int j = i * 2; j < n; j += i)
                {
                    ++cnt;
                    vec[j] = false;
                    if(nums.find(j) != nums.end())
                    {
                        it -> change_weight(j);
                        it -> merge(j, i);
                    }
                }
            }
        }
    }
};
Share