「LeetCode」0952-Largest Component Size by Common Factor（Go）
2024-08-24 14:27:31
分析
注意到要求的是最大的连通分量，那么我们可以先打素数表（唯一分解定理），然后对每个要求的数，将他们同分解出的质因子相连（维护一个并查集），然后求出最大的联通分量即可。
这里使用了筛法求素数。初始化内存时利用了一个hack。
代码
var isPrime[100005] bool
var pa[100005] int
var primeMap=[]int{}
func initPrimeNumbers() {
isPrime[0]=true
for bp:=1;bp<len(isPrime); bp*=2 {
copy(isPrime[bp:], isPrime[:bp])
}
isPrime[0]=false
isPrime[1]=false
for i:=2;i<=100000;i++ {
if(isPrime[i]) {
primeMap=append(primeMap, i)
for j:=i*i; j<=100000; j+=i {
isPrime[j]=false;
}
}
}
}
func find_pa(x int) int {
if(x==pa[x]) {
return x
} else {
pa[x]=find_pa(pa[x])
return pa[x]
}
}
func union_pa(x,y int) {
var pa_x=find_pa(x)
var pa_y=find_pa(y)
if(pa_x!=pa_y) {
pa[pa_x]=pa_y
}
}
func largestComponentSize(A []int) int {
initPrimeNumbers();
for i:=1; i<=100000; i++ {
pa[i]=i
}
for _, i := range A {
var tmp=i
for _,prime := range primeMap {
if(prime>tmp) {
break
}
if(tmp%prime==0) {
for tmp%prime==0 {
tmp/=prime
}
union_pa(i,prime)
}
}
}
cntMap:=make(map[int]int)
var maxVal=0
for _, i :=range A {
var idx=find_pa(i)
if _,ok :=cntMap[idx]; ok {
cntMap[idx]+=1
} else {
cntMap[idx]=1
}
if maxVal<cntMap[idx] {
maxVal=cntMap[idx]
}
}
return maxVal
}
最新文章
- PHP的反射机制
- .NET 多语言支持解决方案(转)
- Mac 制作 10.11.3 U盘安装盘
- win10内网外网智能访问
- BroadcastReceiver的简介
- 【Struts 2】Struts2环境搭建
- php Laravel 框架 介绍及安装
- DoesNotExist at /admin/
- 使用java检测网络连接状况
- 面试题之小炼牛刀zip,lambda,map
- Git clone远程目录443：Timed out 问题(go get)
- 【Swift 3.1】iOS开发笔记（四）
- java 利用jsoup 爬取知乎首页问题
- ArcSDE数据库连接(直连、服务连)与GT_Geometry存储配置图解
- nginx https配置记录
- PHP 实现自动加载
- pecan API调用
- STM 软件事务内存——本质是为提高并发，通过事务来管理内存的读写访问以避免锁的使用
- 吴裕雄 实战python编程（1）
- Ansible playbook基础组件介绍