1.题目基本信息
1.1.题目描述
给定一个由不同正整数的组成的非空数组 nums ,考虑下面的图:
- 有 nums.length 个节点,按从 nums[0] 到 nums[nums.length - 1] 标记;
- 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时,nums[i] 和 nums[j]之间才有一条边。
返回 图中最大连通组件的大小。
1.2.题目地址
https://leetcode.cn/problems/largest-component-size-by-common-factor/description
2.解题方法
2.1.解题思路
并查集+求质因数
2.2.解题步骤
第一步,遍历每个数字num,并获取每个数字的各个质因数,将质因数和num在并查集中进行连接到同一个集合中
第二步,遍历,遍历每一个num,获取每个数在并查集中的root,统计相同root的num的个数,个数最大的那个即为最大连通组件的大小
3.解题代码
Python代码
from collections import defaultdict
# # ==> 并查集模板(附优化)
class UnionFind():
def __init__(self):
self.roots={}
# Union优化:存储根节点主导的集合的总节点数
self.rootSizes={}
def add(self,x):
if x not in self.roots:
self.roots[x]=x
self.rootSizes[x]=1
def find(self,x):
root=x
while root != self.roots[root]:
root=self.roots[root]
# 优化:压缩路径
while x!=root:
temp=self.roots[x]
self.roots[x]=root
x=temp
return root
def union(self,x,y):
rootx,rooty=self.find(x),self.find(y)
if rootx!=rooty:
# 优化:小树合并到大树上
if self.rootSizes[rootx]<self.rootSizes[rooty]:
self.roots[rootx]=rooty
self.rootSizes[rooty]+=self.rootSizes[rootx]
else:
self.roots[rooty]=rootx
self.rootSizes[rootx]+=self.rootSizes[rooty]
# 获取一个正整数的各个分解的质因素及数量;生成的item为(质因数,数量)
def getNumFactors(num):
factor=2
while factor*factor<=num:
if num%factor==0:
cnt=0
while num%factor==0:
cnt+=1
num=num//factor
yield (factor,cnt)
factor+=1
if num>1:
yield (num,1)
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
uf=UnionFind()
for num in nums:
if num==1:
continue
for factor,_ in getNumFactors(num):
uf.add(num)
uf.add(factor)
uf.union(num,factor)
result=0
cntMap=defaultdict(int)
for num in nums:
if num==1:
continue
numRoot=uf.find(num)
cntMap[numRoot]+=1
result=max(result,cntMap[numRoot])
# print(result)
return result