### 歡迎訪問我的GitHub > 這裡分類和彙總了欣宸的全部原創(含配套源碼)：[https://github.com/zq2599/blog_demos](https://github.com/zq2599/blog_demos) ### 本篇概覽 - 本文是《LeetCode952三部曲之三 ...
歡迎訪問我的GitHub
這裡分類和彙總了欣宸的全部原創(含配套源碼)：https://github.com/zq2599/blog_demos
本篇概覽
- 本文是《LeetCode952三部曲之三》的終篇，先回顧一下前文的成果，看看我們之前已經優化到什麼程度：
- 前文的優化思路是減小並查集數組的規模，帶來的結果是節省記憶體、減少數組相關的執行次數，但從代碼上分析，並查集數組處理所占比重並不多，所以造成此處整體優化效果一般
- 所以，除了並查集，還要去尋找其他優化點，這就是本篇的主要內容
優化思路
- 尋找優化點的方向很明確：重點關註時間複雜度高的代碼塊
- 按照上述思路，很容易就找到了下圖中的代碼段，位於程式入口位置，計算每個數字的質因數，因為涉及到素數，所以時間複雜度較高，三個耗時操作是嵌套關係
- 上述方法的思路對每個數字做計算，找出質因數，例如找出99的質因數，需要從2開始一次次計算得出
- 但實際上還有一個更簡單的思路：99以內的質數是固定的25個，這25個中，其平方小於99的只有四個，既：2，3，5，7，所以尋找99的質即因數，就在這四個中找即可（漏掉的11，在後面的代碼中會特別處理找回來）
- 基於以上思路，計算質因數的代碼就很簡單了：
- 提前把100000以內的所有素數都找出來，放在名為primes的數組中
- 對於任意一個數字N，都用primes中的數字去做除法，能整除的就是N的質因數
- 記得像前面的99漏掉了11那樣，把11找回來
編碼
- 接下來的代碼，在前文的基礎上修改
- 首先增加三個靜態變數，註釋已詳細說明其作用：
// isPrime[3]=0，表示數字3是素數，isPrime[4]=1，表示數字4不是素數
private static int[] isPrime = new int[100001];
// 0-100001之間所有的素數都放入這裡
private static int[] primes = new int[100001];
// 素數的數量，也就是primes中有效數據的長度
private static int primeNum = 0;
- 然後是一個靜態代碼塊，一次性算處100000範圍內所有素數，埃式或者歐拉式都可以，這裡用了歐拉式
static {
// 歐拉篩
for(int i=2;i<=100000;i++) {
if(isPrime[i]==0) {
// i是素數，就放入primes數組中
// 更新primes中素數的數量
primes[primeNum++] = 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中
}
- 上述代碼只會在類載入後執行一次，執行完畢後，1到100000之間的所有素數都計算出來並放入primes中，數量是primeNum，在後面的計算中直接拿來用即可
- 接下來是最關鍵的地方了，前面截圖中對每個數字計算質因數的代碼，可以替換掉了，新的代碼如下，可見邏輯已經簡化了，從數組primes中取出來做除法即可：
// 對數組中的每個數，算出所有質因數，構建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);
}
}
- 另外，對於之前99取質因數漏掉了11的問題，上述代碼也有詳細說明：檢查整除結果，大於1的就是漏掉的
- 完整的提交代碼如下
package practice;
import java.util.*;
/**
* @program: leetcode
* @description:
* @author: [email protected]
* @create: 2022-06-30 22:33
**/
public class Solution {
// 並查集的數組， fathers[3]=1的意思是：數字3的父節點是1
// int[] fathers = new int[100001];
int[] fathers;
// 並查集中，每個數字與其子節點的元素數量總和，rootSetSize[5]=10的意思是：數字5與其所有子節點加在一起，一共有10個元素
// int[] rootSetSize = new int[100001];
int[] rootSetSize;
// map的key是質因數，value是以此key作為質因數的數字
// 例如題目的數組是[4,6,15,35]，對應的map就有四個key：2,3,5,7
// key等於2時，value是[4,6]，因為4和6的質因數都有2
// key等於3時，value是[6,15]，因為6和16的質因數都有3
// key等於5時，value是[15,35]，因為15和35的質因數都有5
// key等於7時，value是[35]，因為35的質因數有7
Map<Integer, List<Integer>> map = new HashMap<>();
// 用來保存並查集中，最大樹的元素數量
int maxRootSetSize = 1;
// isPrime[3]=0，表示數字3是素數，isPrime[4]=1，表示數字4不是素數
private static int[] isPrime = new int[100001];
// 0-100001之間所有的素數都放入這裡
private static int[] 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)
