2025-06-25：统计最小公倍数图中的连通块数目。用go语言，你有一个长度为 n 的整数数组 nums 和一个正整数阈值 threshold。

构造一张包含 n 个节点的无向图，其中第 i 个节点对应 nums[i] 的值。若任意两节点 i 和 j 对应的数值的最小公倍数 lcm(nums[i], nums[j]) 不超过 threshold，那么这两个节点之间存在一条无向边。

请你计算这张图中连通块（即图中任意两个节点之间存在路径，且连通块与图中其他节点没有边相连的最大子图）的数量。

这里，最小公倍数 lcm(a, b) 表示两个数 a 和 b 的最小公倍数。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

nums 中所有元素互不相同。

1 <= threshold <= 2 * 100000。

题目来自力扣3378。

解决步骤

1. 1. 初始化并查集：
2. o 使用并查集（Disjoint Set Union, DSU）来管理连通块。初始时，每个节点是自己的父节点，连通块数量为 n（数组长度）。
3. 2. 预处理数字的索引：
4. o 创建一个数组 idx，其中idx[x]表示数字x在nums中的索引（如果x存在于nums中）。这里idx的大小为threshold + 1，因为只有x <= threshold的数字才可能参与 LCM 计算（因为 LCM(a, b) >= max(a, b)，所以如果a或b大于threshold，LCM 必然大于threshold）。
5. 3. 枚举可能的 GCD 值：
6. o 对于每个可能的 GCD 值 g（从 1 到 threshold），我们尝试找到所有数字对 (x, y)，其中 gcd(x, y) = g，且 lcm(x, y) = x * y / g <= threshold。
7. o 由于 lcm(x, y) = x * y / g <= threshold，可以推导出 x * y <= g * threshold。因此，对于固定的 g，x 和 y 的取值范围是 g 的倍数且 x * y <= g * threshold。
8. 4. 合并连通块：
9. o 对于每个 g，找到最小的 x（即 minX）是 g 的倍数且存在于 nums 中。
10. o 然后遍历所有 y = minX + g, minX + 2g, ... 满足 y <= threshold 且 x * y <= g * threshold。如果 y 存在于 nums 中，就将 x 和 y 所在的连通块合并。
11. o 合并操作通过并查集完成，每次合并会将连通块数量减一。
12. 5. 统计连通块数量：
13. o 最终并查集中的连通块数量即为答案。

时间复杂度

• o 并查集的初始化：O(n)。
• o 预处理 idx 数组：O(n + threshold)。
• o 外层循环枚举 g：O(threshold)。
• o 内层循环枚举 y：对于每个 g，y 的取值最多是 threshold / g，因此内层循环的总次数是 threshold/1 + threshold/2 + ... + threshold/threshold ≈ threshold * log(threshold)（调和级数）。
• o 并查集的 find 和 union 操作近似 O(α(n))，其中 α 是反阿克曼函数，可以认为是常数。
• o 总时间复杂度：O(n + threshold * log(threshold))。

额外空间复杂度

• o 并查集数组 fa：O(n)。
• o idx 数组：O(threshold)。
• o 其他临时变量：O(1)。
• o 总额外空间复杂度：O(n + threshold)。

关键点

• o 通过枚举 GCD 值 g 来高效地找到所有可能的 (x, y) 对，避免直接检查所有数字对。
• o 利用并查集高效管理连通块的合并。
• o 预处理 idx 数组快速判断数字是否存在。

Go完整代码如下：

package main

import (
    "fmt"
)

func countComponents(nums []int, threshold int) int {
    n := len(nums)
    fa := make([]int, n)
    for i := range fa {
        fa[i] = i
    }
    // 非递归并查集
    find := func(x int) int {
        rt := x
        for fa[rt] != rt {
            rt = fa[rt]
        }
        for fa[x] != rt {
            fa[x], x = rt, fa[x]
        }
        return rt
    }

    // 记录每个数的下标
    idx := make([]int, threshold+1)
    for i, x := range nums {
        if x <= threshold {
            idx[x] = i + 1 // 这里 +1 了，下面减掉
        }
    }

    for g := 1; g <= threshold; g++ {
        minX := -1
        for x := g; x <= threshold; x += g {
            if idx[x] > 0 { // idx[x] == 0 表示不存在
                minX = x
                break
            }
        }
        if minX < 0 {
            continue
        }
        fi := find(idx[minX] - 1)
        for y := minX + g; y <= threshold && y <= g*threshold/minX; y += g {
            if idx[y] > 0 {
                fj := find(idx[y] - 1)
                if fj != fi {
                    fa[fj] = fi // 合并 idx[x] 和 idx[y]
                    n--         // 连通块个数减一
                }
            }
        }
    }
    return n
}

func main() {
    nums := []int{2, 4, 8, 3, 9}
    threshold := 5
    fmt.Println(countComponents(nums, threshold))
}

Python完整代码如下：

# -*-coding:utf-8-*-

def count_components(nums, threshold):
    n = len(nums)
    fa = list(range(n))

    def find(x):
        rt = x
        while fa[rt] != rt:
            rt = fa[rt]
        while fa[x] != rt:
            fa[x], x = rt, fa[x]
        return rt

    idx = [0] * (threshold + 1)
    for i, x in enumerate(nums):
        if x <= threshold:
            idx[x] = i + 1  # +1 to avoid zero-index confusion

    components = n
    for g in range(1, threshold + 1):
        min_x = -1
        for x in range(g, threshold + 1, g):
            if idx[x] > 0:
                min_x = x
                break
        if min_x < 0:
            continue
        fi = find(idx[min_x] - 1)
        y = min_x + g
        # g * threshold // min_x works as an upper bound to optimize loop
        # but in python integer division is floor division //
        while y <= threshold and y <= g * threshold // min_x:
            if idx[y] > 0:
                fj = find(idx[y] - 1)
                if fj != fi:
                    fa[fj] = fi
                    components -= 1
            y += g

    return components


if __name__ == "__main__":
    nums = [2, 4, 8, 3, 9]
    threshold = 5
    print(count_components(nums, threshold))

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·