|
/ map.computeIfAbsent(j, key -> new ArrayList<>()).add(nums[i]);
map.computeIfAbsent(j, key -> new ArrayList<>()).add(i);
}
// 从cur中将j的因数全部去掉
while (cur%j==0) {
cur /= j;
}
}
// 能走到这里，cur一定是个质数，
// 因为nums[i]被除过多次后结果是cur，所以nums[i]能被cur整除，所以cur是nums[i]的质因数，应该放入map中
if (cur!=1) {
// map.computeIfAbsent(cur, key -> new ArrayList<>()).add(nums[i]);
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;
}
}
- 写完代码，提交LeetCode，顺利AC，咱们将优化前和优化后的数据放在一起对比一下，如下图，左边是优化前，右边是优化后，虽然不能算大幅度提升，但勉强算是有明显提升了
- 至此，第一次优化就完成了，超过50%的成绩依旧很一般，还能进一步提升吗？大幅度提升那种
- 答案自然是可以，感谢咱们这两篇的努力，让我们对解题思路有了深刻理解，接下来，期待第三篇吧，我们会来一次更有效的优化
- 剧透一下：优化点和算素数有关
欢迎访问我的GitHub
这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos
欢迎关注博客园：程序员欣宸
学习路上，你不孤单，欣宸原创一路相伴...
|