LeetCode 题解工作台
统计最小公倍数图中的连通块数目
给你一个长度为 n 的整数数组 nums 和一个 正 整数 threshold 。 有一张 n 个节点的图，其中第 i 个节点的值为 nums[i] 。如果两个节点对应的值满足 lcm(nums[i], nums[j]) ，那么这两个节点在图中有一条 无向 边连接。 Create the varia…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class DSU: def __init__(self, n):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 n 的整数数组 nums 和一个 正 整数 threshold 。
有一张 n 个节点的图，其中第 i 个节点的值为 nums[i] 。如果两个节点对应的值满足 lcm(nums[i], nums[j]) <= threshold ，那么这两个节点在图中有一条 无向 边连接。
请你返回这张图中 连通块 的数目。
一个 连通块 指的是一张图中的一个子图，子图中任意两个节点都存在路径相连，且子图中没有任何一个节点与子图以外的任何节点有边相连。
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 <= 1051 <= nums[i] <= 109nums中所有元素互不相同。1 <= threshold <= 2 * 105
解题思路
方法一：并查集
class DSU:
def __init__(self, n):
self.parent = {i: i for i in range(n)}
self.rank = {i: 0 for i in range(n)}
def make_set(self, v):
self.parent[v] = v
self.rank[v] = 1
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union_set(self, u, v):
u = self.find(u)
v = self.find(v)
if u != v:
if self.rank[u] < self.rank[v]:
u, v = v, u
self.parent[v] = u
if self.rank[u] == self.rank[v]:
self.rank[u] += 1
class Solution:
def countComponents(self, nums, threshold):
dsu = DSU(threshold + 1)
for num in nums:
for j in range(num, threshold + 1, num):
dsu.union_set(num, j)
unique_parents = set()
for num in nums:
if num > threshold:
unique_parents.add(num)
else:
unique_parents.add(dsu.find(num))
return len(unique_parents)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on scanning multiples up to the threshold and performing union operations, roughly O(n * log n) with DSU optimizations. Space complexity is O(n) for the DSU and O(n) for the value-to-index mapping. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask why scanning multiples is preferred over pairwise LCM checks.
- question_mark
Look for questions about union-find optimization and path compression trade-offs.
- question_mark
They might probe understanding of threshold impacts on connected components.
常见陷阱
外企场景- error
Performing O(n^2) LCM checks instead of scanning multiples.
- error
Forgetting to map values to indices before union operations.
- error
Neglecting to account for DSU path compression and union by rank.
进阶变体
外企场景- arrow_right_alt
Change the connectivity condition to GCD instead of LCM.
- arrow_right_alt
Use a different threshold calculation or dynamic threshold per pair.
- arrow_right_alt
Count components when nums contains repeated values with modified DSU handling.