力扣第 113 场周赛第 4 题
题目
给定一个由不同正整数的组成的非空数组 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 中所有值都 不同
相似问题：
分析
#1
- 典型的并查集，问题在于不能二重遍历
- 可以考虑直接遍历公因数 x，遍历 x 的倍数 y，如果 y 在 nums 中，就和 x 相连
- 这样总时间是调和级数，趋于 O(n logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
def find(x):
if f[x] != x:
f[x] = find(f[x])
return f[x]
def union(x,y):
f[find(x)] = find(y)
ma = max(nums)+1
f = list(range(ma))
vis = set(nums)
for x in range(2,ma):
for y in range(x,ma,x):
if y in vis:
union(x,y)
return max(Counter(find(x) for x in nums).values())
|
2122 ms
#2
- 还可以只枚举质数作为公因数 p
- 质数可以用埃氏筛预处理
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
M = 10**5+1
f = [1]*M
for i in range(2,isqrt(M)+1):
if f[i]:
f[i*i:M:i] = [0] * ((M-1-i*i)//i+1)
primes = [i for i in range(2,M) if f[i]]
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
def find(x):
if f[x] != x:
f[x] = find(f[x])
return f[x]
def union(x,y):
f[find(x)] = find(y)
ma = max(nums)+1
f = list(range(ma))
vis = set(nums)
for x in primes:
if x>ma:
break
for y in range(x,ma,x):
if y in vis:
union(x,y)
return max(Counter(find(x) for x in nums).values())
|
608 ms