LeetCode952三部曲之二：小幅度優化(137ms -＞ 122ms，超39% -＞ 超51%)
2023-09-03 21:02:38
歡迎存取我的GitHub
這裡分類和彙總了欣宸的全部原創(含配套原始碼)：https://github.com/zq2599/blog_demos
本篇概覽
- 本文是《LeetCode952三部曲》系列之二，在前文中，咱們詳細分析瞭解題思路，然後按照思路寫出了程式碼，在LeetCode提交成功，成績如下圖所示，137ms，超過39%
- 不得不說這個成績很不理想，於是今天咱們來嘗試進行優化，以減低時間，提升百分比
優化點預判
- 回顧一下題目要求，如下所示
- 上圖中有個重要條件：入引陣列中，最大值不超過100000
- 回顧咱們在初始化並查集資料結構的時候，需要滿足陣列下標代表數位身分這個特性，例如fathers[100000]=123的含義是數位100000的父節點是123，所以陣列長度必須是100001，程式碼如下
int[] fathers = new int[100001];
- 而在實際的並查集操作中，如果入參是4,6,15,35這四個數位，那麼fathers這個陣列中真正被我們用到的也就只有fathers[4]、fathers[6]、fathers[15]、fathers[35]這四個元素，其他100001-4=99997個元素都沒有用到，而程式碼中還要為這些無用的元素分配空間，還要消耗時間去初始化，這是極大的浪費
- 對於另一個陣列rootSetSize，用於記錄下標位置元素的子樹大小，亦是如此，99997個元素也都浪費了
- 以上就是要優化的地方：如果入參是四個數位，那麼fathers和rootSetSize的大小能縮減到四嗎？
- 這就需要分析一下了
優化分析
-
先回顧一下解題思路，整個流程如下圖所示
-
假設此題的入參是這四個數位：4，6，15, 35，回顧什麼時候咱們會用到這四個數位，顯然計算每個數位的質因數的時候必然會用到，計算完成後，得到了下圖的關係（這是前文的內容）
-
然後，咱們根據上圖，得到了每個質因數對應的數位集合，也就是下圖
-
看著上圖，重點來了：從上圖開始，再到後面的並查集操作，再到最終的結束，都不會用4、6、15、35這樣的數位去計算什麼了
-
所以，上面那幅圖中的4、6、15、35，是不是可以替換成他們在入引陣列中的下標？假設入引陣列是[4,6,15,35]，他們的陣列下標就分別是：0、1、2、3
-
將數位替換成陣列下標後，上面那幅圖的內容就有了變化，變成了下圖的樣子，之前的[4,6,15,35]四個數位變成了[0,1,2,3]
-
接下來的並查集操作中，也可以用[0,1,2,3]取代[4,6,15,35]也可以嗎？
-
當然可以，之前是合併4和6，現在變成了合併0和1，題目是要的是連通的數量，而某個唯一的數位到底是4還是它的陣列下標0，這不重要了，重要的是合併不能有錯就行
-
這樣替換後，如果入參是四個數位，不論值是多少，在並查集操作時，只需要用到它們的陣列下標：0、1、2、3，最大也只有3
-
這就有意思了，陣列fathers和rootSetSize的大小從100001變成了入引陣列的長度！
-
準備工作完成了，可以正式動手優化了
優化程式碼
- 首先，要修改的是定義fathers和rootSetSet的程式碼，之前是建立固定長度的陣列，現在改成先不建立，而是等到後面知道入引陣列長度的時候再說
- 然後是largestComponentSize方法中的內容，如下圖，存入map的時候，以前存入的是入參的數位，現在傳入的是數位對應的陣列下標
- 最後還看到一些程式碼略有瑕疵，於是順手改了，如下圖，其實影響不大
- 以上就是改動的全部了
- 最後附上優化後的完整原始碼
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;
/**
* 帶壓縮的並查集查詢(即尋找指定數位的根節點)
* @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];
for (int j=2;j*j<=cur;j++) {
// 從2開始逐個增加，能整除的一定是質數
if(cur%j==0) {
// 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