LeetCode952三部曲之二：小幅度優化(137ms-＞122，超39%-＞51%)

歡迎通路我的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%的成績依舊很一般，還能進一步提升嗎？大幅度提升那種
• 答案自然是可以，感謝咱們這兩篇的努力，讓我們對解題思路有了深刻了解，接下來，期待第三篇吧，我們會來一次更有效的優化
• 劇透一下：優化點和算素數有關

歡迎關注頭條号：程式員欣宸

• 學習路上，你不孤單，欣宸原創一路相伴...