Hard

题目描述

给你一个大小为 n 的整数数组 nums 和一个正整数 threshold。

有一个由 n 个节点组成的图，第 i 个节点的值为 nums[i]。如果 lcm(nums[i], nums[j]) <= threshold，则图中的两个节点 i 和 j 通过一条无向边连接。

返回这个图中连通分量的数目。

连通分量是图的一个子图，在该子图中任意两个顶点之间都存在路径，并且该子图的顶点与子图外的顶点不共享边。

术语 lcm(a, b) 表示 a 和 b 的最小公倍数。

示例 1：

输入：nums = [2,4,8,3,9], threshold = 5
输出：4
解释：四个连通分量是 (2, 4), (3), (8), (9)。

示例 2：

输入：nums = [2,4,8,3,9,12], threshold = 10
输出：2
解释：两个连通分量是 (2, 3, 4, 8, 9) 和 (12)。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 的所有元素都是唯一的
  • 1 <= threshold <= 2 * 10^5

提示：

  • 使用并查集（DSU）
  • 将一个数字连接到所有小于阈值的倍数

解题思路

解题思路

这道题要求计算 LCM 图中的连通分量数目。两个节点相连当且仅当它们对应数字的最小公倍数不超过阈值。

核心观察

  1. 如果 lcm(a, b) <= threshold，由于 lcm(a, b) >= max(a, b)，所以 a 和 b 都必须 <= threshold
  2. 因此，我们只需要考虑 nums 中不超过 threshold 的数字
  3. 超过 threshold 的数字都是独立的连通分量

算法步骤

  1. 筛选有效数字：只保留 <= threshold 的数字
  2. 使用并查集：对于每个有效数字，找到所有它的倍数（也在有效数字中），并连接它们
  3. 优化连接过程：对于数字 x，遍历它的倍数 2x, 3x, 4x, ... 直到超过 threshold，如果倍数也在数组中，则连接它们

时间复杂度优化

关键在于如何高效地连接数字。我们使用"连接数字到其倍数"的策略：

  • 对于每个数字 x，将它与所有在阈值内的倍数连接
  • 这样可以避免计算每对数字的 LCM

最终答案 = 有效数字的连通分量数 + 超过阈值的数字个数

代码实现

class Solution {
public:
    vector<int> parent;
    
    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) {
            parent[px] = py;
        }
    }
    
    int countComponents(vector<int>& nums, int threshold) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        vector<int> validNums;
        
        for (int num : nums) {
            if (num <= threshold) {
                validNums.push_back(num);
            }
        }
        
        if (validNums.empty()) {
            return nums.size();
        }
        
        parent.resize(threshold + 1);
        for (int i = 0; i <= threshold; i++) {
            parent[i] = i;
        }
        
        for (int num : validNums) {
            for (int multiple = 2 * num; multiple <= threshold; multiple += num) {
                if (numSet.count(multiple)) {
                    unite(num, multiple);
                }
            }
        }
        
        unordered_set<int> components;
        for (int num : validNums) {
            components.insert(find(num));
        }
        
        int invalidCount = nums.size() - validNums.size();
        return components.size() + invalidCount;
    }
};

class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int:
        num_set = set(nums)
        valid_nums = [num for num in nums if num <= threshold]
        
        if not valid_nums:
            return len(nums)
        
        parent = list(range(threshold + 1))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        for num in valid_nums:
            multiple = 2 * num
            while multiple <= threshold:
                if multiple in num_set:
                    unite(num, multiple)
                multiple += num
        
        components = set()
        for num in valid_nums:
            components.add(find(num))
        
        invalid_count = len(nums) - len(valid_nums)
        return len(components) + invalid_count

public class Solution {
    private int[] parent;
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private void Unite(int x, int y) {
        int px = Find(x), py = Find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    public int CountComponents(int[] nums, int threshold) {
        var numSet = new HashSet<int>(nums);
        var validNums = new List<int>();
        
        foreach (int num in nums) {
            if (num <= threshold) {
                validNums.Add(num);
            }
        }
        
        if (validNums.Count == 0) {
            return nums.Length;
        }
        
        parent = new int[threshold + 1];
        for (int i = 0; i <= threshold; i++) {
            parent[i] = i;
        }
        
        foreach (int num in validNums) {
            for (int multiple = 2 * num; multiple <= threshold; multiple += num) {
                if (numSet.Contains(multiple)) {
                    Unite(num, multiple);
                }
            }
        }
        
        var components = new HashSet<int>();
        foreach (int num in validNums) {
            components.Add(Find(num));
        }
        
        int invalidCount = nums.Length - validNums.Count;
        return components.Count + invalidCount;
    }
}

var countComponents = function(nums, threshold) {
    const n = nums.length;
    const parent = Array(n).fill(0).map((_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function union(x, y) {
        const px = find(x);
        const py = find(y);
        if (px !== py) {
            parent[px] = py;
        }
    }
    
    function gcd(a, b) {
        while (b !== 0) {
            const temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    function lcm(a, b) {
        return (a * b) / gcd(a, b);
    }
    
    const validNums = [];
    const indexMap = new Map();
    
    for (let i = 0; i < n; i++) {
        if (nums[i] <= threshold) {
            indexMap.set(nums[i], validNums.length);
            validNums.push(nums[i]);
        }
    }
    
    for (let i = 0; i < validNums.length; i++) {
        for (let j = i + 1; j < validNums.length; j++) {
            if (lcm(validNums[i], validNums[j]) <= threshold) {
                union(i, j);
            }
        }
    }
    
    const components = new Set();
    for (let i = 0; i < n; i++) {
        if (nums[i] <= threshold) {
            components.add(find(indexMap.get(nums[i])));
        } else {
            components.add(i + validNums.length);
        }
    }
    
    return components.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(T log T + n)，其中 T 是 threshold，n 是数组长度。连接倍数的时间复杂度为 O(T log T)，并查集操作为 O(n)
空间复杂度O(T + n)，需要存储并查集数组和哈希集合