Leetcode952. Calculate maximum component size by common factor

题目链接

点我(^_^)

题目大意

比如 nums = [4,6,15,35] 答案就是4,nums = [20,50,9,63] 答案就是2.

解题思路

我的思路是对 nums Prime factorization of each number in the array,Then a union can be maintained for each factor,For a number, all factors after its prime factorization can be regarded as a connected set.In this way, you can maintain and check the set size online.素数筛+质因子分解+并查集,时间复杂度为 O(mlogn),m为数组大小,n为数字大小.

当然,You can also follow the official solution,Direct use and query set maintenance,Every number and every factor is a connected component,Finally, determine who the father of the current number is,And just update the set size.The official time complexity is O(m$\sqrt{n}$).

代码(C++)

我的代码

const int N = 1e5+5;
class Solution {
    
public:
    //核心:n只会被最小质因子筛掉
    int cnt = 0; //素数的个数
    int v[N]; //Store the smallest prime factor of each number
    int prime[N]; //存素数
    int fa[N]; // 并查集父节点
    int size[N]; // 并查集大小

    void get_primes(int n){
    
        for(int i = 2;i <= n; ++i){
    
            if(v[i] == 0){
    
                v[i] = i;
                prime[++cnt] = i;
            }
            for(int j = 1 ; j <= cnt;++j){
    
                if(prime[j] > v[i] || i * prime[j] > n) break;
                v[prime[j] * i] = prime[j];
            }
        }
    }
    // void divide(int n) {
    
    // while (v[n]) {
    
    // printf("%d ", v[n]); // 在前
    // n /= v[n]; //在后
    // }
    // }
    int find(int x)
    {
    
        if(x == fa[x])
            return x;
        else
            return find(fa[x]);
    }
    int largestComponentSize(vector<int>& nums) {
    
        int ans = 1;
        get_primes(100000);
        for(int i=0; i<nums.size(); ++i)
        {
    
            int father = 0;
            while (v[nums[i]])
            {
    
                int now = v[nums[i]];
                if(father == 0)
                {
    
                    father = now;
                    if(fa[father] == 0)
                    {
    
                        fa[father] = father;
                        size[father] = 1;
                    }
                    else
                    {
    
                        size[find(father)] ++;
                        ans = max(ans, size[find(father)]);
                    }
                }
                else
                {
    
                    if(fa[now] == 0)
                    {
    
                        fa[now] = find(father);
                    }
                    else if(find(father) != find(now))
                    {
    
                        size[find(father)] += size[find(now)];
                        ans = max(size[find(father)], ans);
                        fa[find(now)] = find(father);
                    }
                }
                while (nums[i] % now == 0)
                    nums[i] /= now;
            }
        }
        return ans;
    }
};

官方代码

class UnionFind {
    
public:
    UnionFind(int n) {
    
        parent = vector<int>(n);
        rank = vector<int>(n);
        for (int i = 0; i < n; i++) {
    
            parent[i] = i;
        }
    }

    void uni(int x, int y) {
    
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
    
            if (rank[rootx] > rank[rooty]) {
    
                parent[rooty] = rootx;
            } else if (rank[rootx] < rank[rooty]) {
    
                parent[rootx] = rooty;
            } else {
    
                parent[rooty] = rootx;
                rank[rootx]++;
            }
        }
    }

    int find(int x) {
    
        if (parent[x] != x) {
    
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
private:
    vector<int> parent;
    vector<int> rank;
};

class Solution {
    
public:
    int largestComponentSize(vector<int>& nums) {
    
        int m = *max_element(nums.begin(), nums.end());
        UnionFind uf(m + 1);
        for (int num : nums) {
    
            for (int i = 2; i * i <= num; i++) {
    
                if (num % i == 0) {
    
                    uf.uni(num, i);
                    uf.uni(num, num / i);
                }
            }
        }
        vector<int> counts(m + 1);
        int ans = 0;
        for (int num : nums) {
    
            int root = uf.find(num);
            counts[root]++;
            ans = max(ans, counts[root]);
        }
        return ans;
    }
};