当前位置：网站首页>LeetCode 0952.按公因数计算最大组件大小：建图 / 并查集

LeetCode 0952.按公因数计算最大组件大小：建图 / 并查集

2022-07-30 19:16:00 【Tisfy】

【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 * 10⁴
1 <= nums[i] <= 10⁵
nums 中所有值都不同

方法一：建图 + 广搜

首先将数组中的每个数分解因数，用hasThisFactor[i]存放数组中有因素i的数，用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);
            }
        }
    }
    // 自己是自己的因数
    hasThisFactor[t].push_back(t);
    num4Factor[t].push_back(t);
}

之后，遍历每一个可能的因数，并开始广搜

广搜过程中，记录每一个因数/每一个元素是否被搜索过

如果遍历到了一个未被搜索过的因数，就以此因数为起点，开始广搜建图。

拓展依据所有拥有这个因数的数( $j = ha s T hi s F a c t or [i]$ )的所有的因数( $n u m 4 F a c t or [j]$ )

// 开始建图
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;  // 从这个节点开始建图，初始时图中元素个数为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;

时间复杂度 $O(N\times \sqrt{M})$ ，其中 $N$ 是数组中元素的个数， $M$ 是数组中元素的最大值(上述算法中没有统计这 $N$ 个元素的最大值，因此按 $10^5$ 来处理了)。遍历过程中，每个因数/元素只会被真正地处理一次和被遍历数次
空间复杂度 $O(N\times Q + M)$ ，其中 $Q$ 是数组中元素的平均质因数的个数

AC代码

C++

class Solution {
    
public:
    int largestComponentSize(vector<int>& nums) {
    
        // 分解因数到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);
                    }
                }
            }
            // 自己是自己的因数
            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;
    }
};

方法二：并查集

并查集的思路较为简单，把每个数的所有因数和这个数合并到一个集合中，然后统计每个集合中有多少个元素，返回最大的元素个数即可。

这里用到了自己写的并查集类UnionFind，构造时传入最大元素个数，合并x和y时调用Union(int x, int y)函数，想得到x所在集合的根时调用find(int x)函数即可很方便地使用。

时间复杂度 $O(N\times \sqrt{M} \times \alpha(N))$ ，其中 $N$ 是数组中元素的个数， $M$ 是数组中元素的最大值， $\alpha(N)$ 是平均一次并查集操作的时间复杂度（其中 $\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) {
    
        // 并查集构建
        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);
                }
            }
        }
        // 统计有几个集合、每个集合中有多少个元素
        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;
    }
};