|
] primes = new int[100001];
// 素数的数量，也就是primes中有效数据的长度
private static int primeNum = 0;
static {
// 欧拉筛
for(int i=2;i<=100000;i++) {
if(isPrime[i]==0) {
// i是素数，就放入primes数组中
// 更新primes中素数的数量
primes[primeNum++] = i;
System.out.println(i + "-" + i*i);
}
for(int j=0;i*primes[j]<=100000;j++) {
// primes[j]*i的结果是个乘积，这样的数字显然不是素数，所以在isPrimes数组中标注为1
isPrime[primes[j]*i] = 1;
// 如果i是primes中某个素数的倍数，就没有必要再计算了，退出算下一个，
// 例如i=8的时候，其实在之前i=4时就已经计算出8不是素数了
if(i%primes[j]==0) {
break;
}
}
}
// 经过以上代码，0-100001之间所有素数都放入了primes中
}
/**
* 带压缩的并查集查找(即寻找指定数字的根节点)
* @param i
*/
private int find(int i) {
// 如果执向的是自己，那就是根节点了
if(fathers[i]==i) {
return i;
}
// 用递归的方式寻找，并且将整个路径上所有长辈节点的父节点都改成根节点，
// 例如1的父节点是2，2的父节点是3，3的父节点是4，4就是根节点，在这次查找后，1的父节点变成了4，2的父节点也变成了4，3的父节点还是4
fathers[i] = find(fathers[i]);
return fathers[i];
}
/**
* 并查集合并，合并后，child会成为parent的子节点
* @param parent
* @param child
*/
private void union(int parent, int child) {
int parentRoot = find(parent);
int childRoot = find(child);
// 如果有共同根节点，就提前返回
if (parentRoot==childRoot) {
return;
}
// child元素根节点是childRoot，现在将childRoot的父节点从它自己改成了parentRoot，
// 这就相当于child所在的整棵树都拿给parent的根节点做子树了
fathers[childRoot] = fathers[parentRoot];
// 合并后，这个树变大了，新增元素的数量等于被合并的字数元素数量
rootSetSize[parentRoot] += rootSetSize[childRoot];
// 更像最大数量
maxRootSetSize = Math.max(maxRootSetSize, rootSetSize[parentRoot]);
}
public int largestComponentSize(int[] nums) {
// 对数组中的每个数，算出所有质因数，构建map
for (int i=0;i<nums.length;i++) {
int cur = nums[i];
// cur的质因数一定是primes中的一个
for (int j=0;j<primeNum && primes[j]*primes[j]<=cur;j++) {
if (cur%primes[j]==0) {
map.computeIfAbsent(primes[j], key -> new ArrayList<>()).add(i);
// 要从cur中将primes[j]有关的倍数全部剔除，才能检查下一个素数
while (cur%primes[j]==0) {
cur /= primes[j];
}
}
}
// 能走到这里依然不等于1，是因为for循环中的primes[j]*primes[j]<<=cur导致了部分素数没有检查到，
// 例如6，执行了for循环第一轮后，被2除过，cur等于3，此时j=1,那么primes[j]=3，因此 3*3无法小于cur的3，于是退出for循环，
// 此时cur等于3，应该是个素数，所以nums[i]就能被此时的cur整除，那么此时的cur就是nums[i]的质因数，也应该放入map
if (cur>1) {
map.computeIfAbsent(cur, key -> new ArrayList<>()).add(i);
}
}
fathers = new int[nums.length];
rootSetSize = new int[nums.length];
// 至此，map已经准备好了，接下来是并查集的事情，先要初始化数组
for(int i=0;i< fathers.length;i++) {
// 这就表示：数字i的父节点是自己
fathers[i] = i;
// 这就表示：数字i加上其下所有子节点的数量等于1（因为每个节点父节点都是自己，所以每个节点都没有子节点）
rootSetSize[i] = 1;
}
// 遍历map
for (int key : map.keySet()) {
// 每个key都是一个质因数
// 每个value都是这个质因数对应的数字
List<Integer> list = map.get(key);
int size = list.size();
// 超过1个元素才有必要合并
if (size>1) {
// 取第0个元素作为父节点
int parent = list.get(0);
// 将其他节点全部作为地0个元素的子节点
for(int i=1;i<size;i++) {
union(parent, list.get(i));
}
}
}
return maxRootSetSize;
}
}
- 改动完成，提交试试，如下图，左边是前文的成绩，右边是本次优化后的成绩，从122ms优化到96ms，从超51%优化到超91%，优化效果明显
- 至此，《LeetCode952三部曲》全部完成，如果您正在刷题，希望此系列能给您一些参考
欢迎访问我的GitHub
这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos
欢迎关注博客园：程序员欣宸
学习路上，你不孤单，欣宸原创一路相伴...05086920)
|