Hard

题目描述

给定一个由不同正整数组成的数组 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^4
  • 1 <= nums[i] <= 10^5
  • nums 的所有值都是唯一的

解题思路

这道题要求找出由公因数连接的最大连通分量。关键思路是使用并查集来维护连通性。

核心思想：

  1. 如果两个数有大于1的公因数，它们就应该在同一个连通分量中
  2. 我们可以通过质因数分解来建立连接关系
  3. 对于每个数，找出它的所有质因数，然后将这个数与它的每个质因数建立连接

算法步骤：

  1. 使用并查集数据结构
  2. 为每个数字找出所有质因数
  3. 将每个数字与其质因数在并查集中合并
  4. 最后统计每个连通分量的大小，返回最大值

优化细节：

  • 只需要考虑到√n的因数，因为大于√n的质因数最多只有一个
  • 使用哈希表记录质因数对应的数字，避免重复计算
  • 并查集使用路径压缩和按秩合并优化

时间复杂度主要来自质因数分解，对于每个数字最多需要O(√nums[i])的时间。

代码实现

class Solution {
public:
    vector<int> parent, size;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (size[px] < size[py]) swap(px, py);
        parent[py] = px;
        size[px] += size[py];
    }
    
    int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        int maxVal = *max_element(nums.begin(), nums.end());
        
        parent.resize(maxVal + 1);
        size.resize(maxVal + 1, 1);
        iota(parent.begin(), parent.end(), 0);
        
        unordered_map<int, int> factorToNum;
        
        for (int num : nums) {
            int temp = num;
            for (int i = 2; i * i <= temp; i++) {
                if (temp % i == 0) {
                    if (factorToNum.count(i)) {
                        unite(num, factorToNum[i]);
                    } else {
                        factorToNum[i] = num;
                    }
                    while (temp % i == 0) {
                        temp /= i;
                    }
                }
            }
            if (temp > 1) {
                if (factorToNum.count(temp)) {
                    unite(num, factorToNum[temp]);
                } else {
                    factorToNum[temp] = num;
                }
            }
        }
        
        unordered_map<int, int> componentSize;
        for (int num : nums) {
            componentSize[find(num)]++;
        }
        
        int maxSize = 0;
        for (auto& [root, sz] : componentSize) {
            maxSize = max(maxSize, sz);
        }
        
        return maxSize;
    }
};

class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
        
        max_val = max(nums)
        parent = list(range(max_val + 1))
        rank = [0] * (max_val + 1)
        
        factor_to_num = {}
        
        for num in nums:
            temp = num
            i = 2
            while i * i <= temp:
                if temp % i == 0:
                    if i in factor_to_num:
                        union(num, factor_to_num[i])
                    else:
                        factor_to_num[i] = num
                    while temp % i == 0:
                        temp //= i
                i += 1
            
            if temp > 1:
                if temp in factor_to_num:
                    union(num, factor_to_num[temp])
                else:
                    factor_to_num[temp] = num
        
        component_size = {}
        for num in nums:
            root = find(num)
            component_size[root] = component_size.get(root, 0) + 1
        
        return max(component_size.values())

public class Solution {
    private int[] parent, rank;
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private void Union(int x, int y) {
        int px = Find(x), py = Find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) {
            (px, py) = (py, px);
        }
        parent[py] = px;
        if (rank[px] == rank[py]) {
            rank[px]++;
        }
    }
    
    public int LargestComponentSize(int[] nums) {
        int maxVal = nums.Max();
        parent = new int[maxVal + 1];
        rank = new int[maxVal + 1];
        for (int i = 0; i <= maxVal; i++) {
            parent[i] = i;
        }
        
        var factorToNum = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int temp = num;
            for (int i = 2; i * i <= temp; i++) {
                if (temp % i == 0) {
                    if (factorToNum.ContainsKey(i)) {
                        Union(num, factorToNum[i]);
                    } else {
                        factorToNum[i] = num;
                    }
                    while (temp % i == 0) {
                        temp /= i;
                    }
                }
            }
            if (temp > 1) {
                if (factorToNum.ContainsKey(temp)) {
                    Union(num, factorToNum[temp]);
                } else {
                    factorToNum[temp] = num;
                }
            }
        }
        
        var componentSize = new Dictionary<int, int>();
        foreach (int num in nums) {
            int root = Find(num);
            componentSize[root] = componentSize.GetValueOrDefault(root, 0) + 1;
        }
        
        return componentSize.Values.Max();
    }
}

var largestComponentSize = function(nums) {
    const parent = new Map();
    const size = new Map();
    
    function find(x) {
        if (!parent.has(x)) {
            parent.set(x, x);
            size.set(x, 1);
            return x;
        }
        if (parent.get(x) !== x) {
            parent.set(x, find(parent.get(x)));
        }
        return parent.get(x);
    }
    
    function union(x, y) {
        const px = find(x);
        const py = find(y);
        if (px === py) return;
        
        if (size.get(px) < size.get(py)) {
            parent.set(px, py);
            size.set(py, size.get(py) + size.get(px));
        } else {
            parent.set(py, px);
            size.set(px, size.get(px) + size.get(py));
        }
    }
    
    function getPrimeFactors(n) {
        const factors = [];
        let d = 2;
        while (d * d <= n) {
            while (n % d === 0) {
                factors.push(d);
                n /= d;
            }
            d++;
        }
        if (n > 1) factors.push(n);
        return [...new Set(factors)];
    }
    
    const factorToNums = new Map();
    
    for (const num of nums) {
        const factors = getPrimeFactors(num);
        for (const factor of factors) {
            if (!factorToNums.has(factor)) {
                factorToNums.set(factor, []);
            }
            factorToNums.get(factor).push(num);
        }
    }
    
    for (const numList of factorToNums.values()) {
        for (let i = 1; i < numList.length; i++) {
            union(numList[0], numList[i]);
        }
    }
    
    let maxSize = 1;
    for (const num of nums) {
        const root = find(num);
        maxSize = Math.max(maxSize, size.get(root));
    }
    
    return maxSize;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法
时间复杂度O(n√m + nα(m))
空间复杂度O(m)

其中 n = nums.length，m = max(nums)，α 是反阿克曼函数

相关题目