Daily LeetCode – day0001 0952. Largest Component Size by Common Factor

// 0952. Largest Component Size by Common Factor
class Solution {
    public int largestComponentSize(int[] nums) {
        int maxValue = 0;
        for (int num : nums) {
            if (num > maxValue) {
                maxValue = num;
            }
        }
        UnionFind unionFind = new UnionFind(maxValue + 1);
        for (int num : nums) {
            for (int i = 2; i * i <= num; ++i) {
                if (num % i == 0) {
                    unionFind.union(num, i);
                    unionFind.union(num, num / i);
                }
            }
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            int parentOfNum = unionFind.find(num);
//            if (hashMap.get(parentOfNum) == null) {
//                hashMap.put(parentOfNum, 1);
//            } else {
//                hashMap.put(parentOfNum, hashMap.get(parentOfNum) + 1);
//            }
            hashMap.merge(parentOfNum, 1, Integer::sum);
        }
        int ans = 1;
        for (Integer componentSize : hashMap.values()) {
            if (componentSize > ans) {
                ans = componentSize;
            }
        }
        return ans;
    }
}

class UnionFind {
    private final ArrayList<Integer> parent = new ArrayList<>();

    public UnionFind(int n) {
        for (int i = 0; i < n; ++i) {
            parent.add(i);
        }
    }

    public int find(int son) {
        if (parent.get(son) == son) {
            return son;
        }
        parent.set(son, find(parent.get(son)));
        return parent.get(son);
    }

    public void union(int a, int b) {
        int parentOfA = find(a);
        int parentOfB = find(b);
        if (parentOfA != parentOfB) {
            parent.set(parentOfA, parentOfB);
        }
    }
}

学习笔记：
这是一道并查集的题目，也考查了对于求因数的基本功。
1.
并查集中难写的是find函数，其中递归调用那段最容易卡住。
先从parent中找到目前son的老大，然后对这个老大再递归调用寻找老大的老大，最终找到后将最大的老大设置到parent中索引为son的位置上。在递归的过程中，中间节点的小老大也会被一起指向最大的老大。
2.
这里用了hashmap来存储每一个给的数字最终老大的小弟数量。
如果一开始没有在hashmap里就认为原本是0，设定为1。
否则就将原本的数字加上1。
这一段我写的比较朴素，使用了if-else语句。但有存在两种高级写法。
merge函数是一种，这个会比较难以理解，还用到了lambda表达式。
getOrDefault函数时另一种，这个函数特别好理解，有就get没有就按default来。