LeetCode 0952. Calculate Maximum Component Size by Common Factor: Mapping / Union Search

【LetMeFly】952.按公因数计算最大组件大小：建图 / 并查集

力扣题目链接：https://leetcode.cn/problems/largest-component-size-by-common-factor/

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

方法一：建图 + 广搜

First factor each number in the array,用hasThisFactor[i]There are factors in the storage arrayi的数,用num4Factor[i]存放数组中的元素i的所有的因数.

vector<vector<int>> hasThisFactor(100010);
vector<vector<int>> num4Factor(100010);
for (int t : nums) {
    
    int k = sqrt(t);
    for (int i = 2; i <= k; i++) {
    
        if (t % i == 0) {
    
            hasThisFactor[i].push_back(t);
            num4Factor[t].push_back(i);
            if (t / i != i) {
    
                hasThisFactor[t / i].push_back(t);
                num4Factor[t].push_back(t / i);
            }
        }
    }
    // oneself is one's own factor
    hasThisFactor[t].push_back(t);
    num4Factor[t].push_back(t);
}

之后,Iterate over every possible factor,and start searching

During the search process,Record each factor/Whether each element has been searched

If it traverses to an unsearched factor,Take this factor as a starting point,Start to search and build maps.

Extend by all numbers with this factor($j=hasThisFactor[i]$)的所有的因数($num4Factor[j]$)

// 开始建图
int ans = 0;
vector<bool> visitedFactor(100010, false);  // 标记是否遍历过
vector<bool> visitedNum(100010, false);
for (int i = 2; i <= 100000; i++) {
      // Iterate over all possible factors
    if (hasThisFactor[i].size() && !visitedFactor[i]) {
      // 有 elements with this factor && has not been traversed
        visitedFactor[i] = true;  // Then this has been traversed
        int thisAns = 0;  // Start building the graph from this node,Initially, the number of elements in the graph is 0
        queue<int> q;  // 广搜队列
        q.push(i);
        while (q.size()) {
    
            int thisFactor = q.front();  // Take out a factor
            q.pop();
            for (int thisNum : hasThisFactor[thisFactor]) {
      // Iterate over all elements with this factor
                if (!visitedNum[thisNum]) {
      // A new untraversed element
                    visitedNum[thisNum] = true;  // 标记为遍历过
                    thisAns++;  // The number of elements in the graph++
                    for (int thisNewFactor : num4Factor[thisNum]) {
      // Iterate over all factors of this element（can be connected to a graph）
                        if (!visitedFactor[thisNewFactor]) {
      // Untraversed factors
                            visitedFactor[thisNewFactor] = true;  // 标记为遍历过
                            q.push(thisNewFactor);  // 入队
                        }
                    }
                }
            }
        }
        ans = max(ans, thisAns);  // Update answer max
    }
}
return ans;

• 时间复杂度$O(N\times \sqrt{M})$,其中$N$是数组中元素的个数,$M$is the maximum value of elements in the array(This is not counted in the above algorithm$N$个元素的最大值,因此按$10^5$来处理了).遍历过程中,each factor/Elements are only really processed once and traversed several times
• 空间复杂度$O(N\times Q+M)$,其中$Q$is the average number of prime factors of the elements in the array

AC代码

C++

class Solution {
    
public:
    int largestComponentSize(vector<int>& nums) {
    
        // Decomposition factor to hasThisFactor中
        vector<vector<int>> hasThisFactor(100010);
        vector<vector<int>> num4Factor(100010);
        for (int t : nums) {
    
            int k = sqrt(t);
            for (int i = 2; i <= k; i++) {
    
                if (t % i == 0) {
    
                    hasThisFactor[i].push_back(t);
                    num4Factor[t].push_back(i);
                    if (t / i != i) {
    
                        hasThisFactor[t / i].push_back(t);
                        num4Factor[t].push_back(t / i);
                    }
                }
            }
            // oneself is one's own factor
            hasThisFactor[t].push_back(t);
            num4Factor[t].push_back(t);
        }
        // 开始建图
        int ans = 0;
        vector<bool> visitedFactor(100010, false);
        vector<bool> visitedNum(100010, false);
        for (int i = 2; i <= 100000; i++) {
    
            if (hasThisFactor[i].size() && !visitedFactor[i]) {
    
                visitedFactor[i] = true;
                int thisAns = 0;
                queue<int> q;
                q.push(i);
                while (q.size()) {
    
                    int thisFactor = q.front();
                    q.pop();
                    for (int thisNum : hasThisFactor[thisFactor]) {
    
                        if (!visitedNum[thisNum]) {
    
                            visitedNum[thisNum] = true;
                            thisAns++;
                            for (int thisNewFactor : num4Factor[thisNum]) {
    
                                if (!visitedFactor[thisNewFactor]) {
    
                                    visitedFactor[thisNewFactor] = true;
                                    q.push(thisNewFactor);
                                }
                            }
                        }
                    }
                }
                ans = max(ans, thisAns);
            }
        }
        return ans;
    }
};

方法二：并查集

The idea of ​​​​consolidation is relatively simple,Combine all the factors of each number with the number into a set,Then count how many elements are in each set,Return the maximum number of elements.

Here, the union check class I wrote myself is usedUnionFind,The maximum number of elements is passed in during construction,合并x和y时调用Union(int x, int y)函数,想得到xCalled when the root of the collection is infind(int x)function can be easily used.

• 时间复杂度$O(N\times \sqrt{M}\times \alpha (N))$,其中$N$是数组中元素的个数,$M$is the maximum value of elements in the array,$\alpha (N)$is the average time complexity of a union-find operation（其中$\alpha$是反阿克曼函数）.
• 空间复杂度$O(M)$

AC代码

C++

class UnionFind {
    
private:
    int* father;
    int* rank;
public:
    UnionFind(int n) {
    
        father = new int[n];
        rank = new int[n];
        memset(rank, 0, sizeof(rank));
        for (int i = 0; i < n; i++) {
    
            father[i] = i;
        }
    }
    
    ~UnionFind() {
    
        delete[] father;
        delete[] rank;
    }

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

    void Union(int x, int y) {
    
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
    
            if (rank[rootX] > rank[rootY]) {
    
                father[rootY] = rootX;
            }
            else if (rank[rootX] < rank[rootY]) {
    
                father[rootX] = rootY;
            }
            else {
    
                father[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

class Solution {
    
public:
    int largestComponentSize(vector<int>& nums) {
    
        // And check the build
        UnionFind unionFind(*max_element(nums.begin(), nums.end()) + 1);
        for (int t : nums) {
    
            int k = sqrt(t);
            for (int i = 2; i <= k; i++) {
    
                if (t % i == 0) {
    
                    unionFind.Union(i, t);
                    unionFind.Union(i, t / i);
                }
            }
        }
        // Statistics have several sets、How many elements are in each set
        unordered_map<int, int> times;
        for (int t : nums) {
    
            times[unionFind.find(t)]++;
        }
        // 统计最大值
        int ans = 0;
        for (auto[root, appendTime] : times) {
    
            ans = max(ans, appendTime);
        }
        return ans;
    }
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126069985