LeetCode 题解工作台
按公因数计算最大组件大小
给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图： 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记； 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时， nums[i] 和 nums[j] 之间才有…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
利用“试除法”，对 中的每个数 分解因数，然后将每个因数 与 合并，$v / i$ 与 合并。此过程用并查集来维护连通分量。 最后，遍历 中每个数 ，找出所在的连通分量，出现次数最多的连通分量就是所求的答案。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个由不同正整数的组成的非空数组 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 * 1041 <= nums[i] <= 105nums中所有值都 不同
解题思路
方法一：数学 + 并查集
利用“试除法”，对 中的每个数 分解因数，然后将每个因数 与 合并， 与 合并。此过程用并查集来维护连通分量。
最后，遍历 中每个数 ，找出所在的连通分量，出现次数最多的连通分量就是所求的答案。
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa != pb:
self.p[pa] = pb
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
uf = UnionFind(max(nums) + 1)
for v in nums:
i = 2
while i <= v // i:
if v % i == 0:
uf.union(v, i)
uf.union(v, v // i)
i += 1
return max(Counter(uf.find(v) for v in nums).values())
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on factorization and union-find operations, roughly O(N sqrt(M)) where N is array length and M is max value. Space complexity is O(N + M) for parent and factor maps. Optimizations like path compression help maintain near-linear performance. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate attempts naive pairwise GCD checks, which is inefficient for large inputs.
- question_mark
Candidate successfully maps numbers to prime factors, indicating understanding of factor-based graph structure.
- question_mark
Candidate applies union-find with path compression or other optimizations to manage large component merging efficiently.
常见陷阱
外企场景- error
Trying to compare every pair with GCD, causing TLE on large arrays.
- error
Forgetting to merge all numbers sharing a factor, leading to undercounting component sizes.
- error
Neglecting path compression, resulting in slower union-find operations and exceeding time limits.
进阶变体
外企场景- arrow_right_alt
Compute largest component size considering only prime numbers in the array.
- arrow_right_alt
Find the number of connected components rather than the largest size using the same factor-based graph.
- arrow_right_alt
Determine largest component size when edges exist for numbers sharing any divisor within a given threshold, not necessarily prime factors.