LeetCode952三部曲之三：再次优化(122ms -＞ 96ms，超51% -＞ 超91%)
欢迎访问我的GitHub这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos
本篇概览
[*]本文是《LeetCode952三部曲之三》的终篇，先回顾一下前文的成果，看看我们之前已经优化到什么程度：
https://img2023.cnblogs.com/blog/485422/202309/485422-20230902115636559-760359198.png
[*]前文的优化思路是减小并查集数组的规模，带来的结果是节省内存、减少数组相关的执行次数，但从代码上分析，并查集数组处理所占比重并不多，所以造成此处整体优化效果一般
[*]所以，除了并查集，还要去寻找其他优化点，这就是本篇的主要内容
优化思路
[*]寻找优化点的方向很明确：重点关注时间复杂度高的代码块
[*]按照上述思路，很容易就找到了下图中的代码段，位于程序入口位置，计算每个数字的质因数，因为涉及到素数，所以时间复杂度较高，三个耗时操作是嵌套关系
https://img2023.cnblogs.com/blog/485422/202309/485422-20230902115636897-1856208502.png
[*]上述方法的思路对每个数字做计算，找出质因数，例如找出99的质因数，需要从2开始一次次计算得出
[*]但实际上还有一个更简单的思路：99以内的质数是固定的25个，这25个中，其平方小于99的只有四个，既：2，3，5，7，所以寻找99的质即因数，就在这四个中找即可（漏掉的11，在后面的代码中会特别处理找回来）
[*]基于以上思路，计算质因数的代码就很简单了：
[*]提前把100000以内的所有素数都找出来，放在名为primes的数组中
[*]对于任意一个数字N，都用primes中的数字去做除法，能整除的就是N的质因数
[*]记得像前面的99漏掉了11那样，把11找回来
编码
[*]接下来的代码，在前文的基础上修改
[*]首先增加三个静态变量，注释已详细说明其作用：
// isPrime=0，表示数字3是素数，isPrime=1，表示数字4不是素数
private static int[] isPrime = new int;
// 0-100001之间所有的素数都放入这里
private static int[] primes = new int;
// 素数的数量，也就是primes中有效数据的长度
private static int primeNum = 0;
[*]然后是一个静态代码块，一次性算处100000范围内所有素数，埃式或者欧拉式都可以，这里用了欧拉式
static { // 欧拉筛 for(int i=2;i
页:
[1]