leetcode每日一题，给定一个由不同正整数的组成的非空数组 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
def find(list,nums):
for m in list:
for k in nums:
if k not in list and math.gcd(k, m) > 1:
list.append(k)
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
list1=[]
for i in nums:
list=[i]
for j in nums:
if i!=j and math.gcd(i,j)>1:
list.append(j)
while True:
a=len(list)
find(list,nums)
b=len(list)
if a==b:
break
list1.append(len(list))
return max(list1)
循环语句太多导致遇到非常长的数字就超出时间限制了。
算法本身能算出正确得数。
请评价一下我的算法，有没有优化空间。
时间复杂度为O(n4),一般超过O(n3)算法上就存在问题。
参考：
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def merge(self, x: int, y: int) -> None:
x, y = self.find(x), self.find(y)
if x == y:
return
if self.rank[x] > self.rank[y]:
self.parent[y] = x
elif self.rank[x] < self.rank[y]:
self.parent[x] = y
else:
self.parent[y] = x
self.rank[x] += 1
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
uf = UnionFind(max(nums) + 1)
for num in nums:
i = 2
while i * i <= num:
if num % i == 0:
uf.merge(num, i)
uf.merge(num, num // i)
i += 1
return max(Counter(uf.find(num) for num in nums).values())