leetcode-952：按公因数计算最大组件大小-阿里云开发者社区

leetcode-952：按公因数计算最大组件大小

2024-01-15 100

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： leetcode-952：按公因数计算最大组件大小

题目

题目连接

给定一个由不同正整数的组成的非空数组 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

解题

方法一：带权重有向图+并查集（超时）

带权重的图+并查集

写法一：

每个节点还带了权重weight[i]，表示直接指向当前节点的节点个数

最后只需要找到权重最大的，就是我们想要的答案。

能直接遍历weight来获得最大的集合元素个数？显然不能直接这么做，还需要对他进行路径压缩，让元素直接指向根节点。

class UnionFind{
private:
    vector<int> parent;
    vector<int> weight;
public:
    UnionFind(int n){
        parent.resize(n);
        weight.resize(n);
        for(int i=0;i<n;i++){
            parent[i]=i;
            weight[i]=1;//直接指向当前节点的数量(包含自身，注意孙子节点，不算直接指向)
        }
    }
    int find(int index){
        if(parent[index]==index) return index;
        int origin=parent[index];
        parent[index]=find(parent[index]);
        weight[parent[index]]++;//指向根节点的节点数量+1
        weight[origin]--;//指向原先节点的节点数量-1
        return parent[index];
    }
    void unite(int index1,int index2){
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){
            parent[p1]=p2;
            weight[p2]++;//指向根节点的节点数量+1
        }
    }
    int findMaxSet(){
        for(int i=0;i<weight.size();i++){
            find(i);
        }
        int res=0;
        for(int i=0;i<weight.size();i++){
            res=max(res,weight[i]);
        }
        return res;
    }
};
class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        int n=nums.size();
        UnionFind uf(n);
        unordered_map<int,int> mp;
        int id=0;
        for(int i=0;i<n;i++){
            if(!mp.count(nums[i])){
                mp[nums[i]]=id++;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int id1=mp[nums[i]];
                int id2=mp[nums[j]];
                if(gcd(nums[i],nums[j])>1){
                    uf.unite(id1,id2);
                }
            }
        }
        return uf.findMaxSet();
    }
};

写法二：

weight表示，指向当前节点的节点数(包含孙子节点等)

只要在unite里面加上另一个子树的所有节点数就行了，find过程中进行的路径压缩，只是调整了指向根节点，但是该根节点的所有节点数是不会变的。

class UnionFind{
private:
    vector<int> parent;
    vector<int> weight;
public:
    UnionFind(int n){
        parent.resize(n);
        weight.resize(n);
        for(int i=0;i<n;i++){
            parent[i]=i;
            weight[i]=1;//指向当前节点的数量（包含孙子节点等）
        }
    }
    int find(int index){
        if(parent[index]==index) return index;
        parent[index]=find(parent[index]);
        return parent[index];
    }
    void unite(int index1,int index2){
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){
            parent[p1]=p2;
            weight[p2]+=weight[p1];//指向根节点的节点数量 加上 子树的节点数量
        }
    }
    int findMaxSet(){
        for(int i=0;i<weight.size();i++){
            find(i);
        }
        int res=0;
        for(int i=0;i<weight.size();i++){
            res=max(res,weight[i]);
        }
        return res;
    }
};
class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        int n=nums.size();
        UnionFind uf(n);
        unordered_map<int,int> mp;
        int id=0;
        for(int i=0;i<n;i++){
            if(!mp.count(nums[i])){
                mp[nums[i]]=id++;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int id1=mp[nums[i]];
                int id2=mp[nums[j]];
                if(gcd(nums[i],nums[j])>1){
                    uf.unite(id1,id2);
                }
            }
        }
        return uf.findMaxSet();
    }
};

主要超时原因还是因为两层for循环

方法二：枚举质因数+并查集

参考链接

基本思路：把关联的加入到并查集中，最后遍历nums，相同的根节点那么数量+1，这样就能找到最多元素的集合了。

由于nums.length最大为2 ∗ 1 0 4 2*10^42∗104lianjie

遍历每个值，两两匹配会超时。

因此采用枚举公因式的方式，如果k>=2，且num%k==0，那么k为公约数，对num和k进行联结，以及num和num/k进行联结。不管k或者num/k有没有在nums中这都不要紧，因为后面遍历nums的时候不会遍历到它们。

相比O ( 4 ∗ 1 0 8 ) O(4*10^8)O(4∗108)的复杂度来的更小。

class UnionFind{
private:
    vector<int> parent;
public:
    UnionFind(int n){
        parent.resize(n);
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }
    int find(int index){
        if(parent[index]==index) return index;
        return parent[index]=find(parent[index]);
    }
    void unite(int index1,int index2){
        int p1=find(index1);
        int p2=find(index2);
        if(p1==p2) return;
        parent[p1]=p2;
    }
};
class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        int maxLength=*max_element(nums.begin(),nums.end());
        int n=nums.size();
        UnionFind uf(maxLength+1);
        for(int num:nums){
            for(int k=sqrt(num);k>=2;k--){
                if(num%k==0){
                    uf.unite(num,k);//不管k属不属于num都没有关系，把他添加到集合中。因为后续还要遍历一遍nums
                    uf.unite(num,num/k);
                }
            }
        }
        vector<int> cnt(maxLength+1);
        int res=0;
        for(int num:nums){//遍历nums中的值，同一集合的+1
            cnt[uf.find(num)]++;
            res=max(res,cnt[uf.find(num)]);
        }
        return res;
    }
};

leetcode-952：按公因数计算最大组件大小

题目

解题

方法一：带权重有向图+并查集（超时）

方法二：枚举质因数+并查集

热门文章

最新文章

相关课程

相关电子书