Largest Component Size by Common Factor (H)

題目

Given a non-empty array of unique positive integers A, consider the following graph:

There are A.length nodes, labelled A[0] to A[A.length - 1];
There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

1 <= A.length <= 20000
1 <= A[i] <= 100000

題意

給定一串正整數，將其中具有相同因數(>=2)的整數兩兩相連，求這樣操作后最大連通分量中結點的數量，

思路

并查集處理，對于每一個整數，找到它所有大于2的因數，將該因數和整數本身添加到一個組中，最后統計每個組中陣列中整數出現的次數即可，

代碼實作

Java

class Solution {
    public int largestComponentSize(int[] A) {
        int maxSize = 0, maxNum = 0;
        // 找到最大整數
        for (int num : A) {
            maxNum = Math.max(maxNum, num);
        }

        Map<Integer, Integer> map = new HashMap<>();
        int[] root = new int[maxNum + 1];
        for (int i = 1; i <= maxNum; i++) {
            root[i] = i;
        }

        for (int num : A) {
            for (int i = 2; i <= (int) Math.sqrt(num); i++) {
                if (num % i == 0) {
                    int j = num / i;
                    union(root, num, i);
                    union(root, num, j);
                }
            }
        }

        for (int num : A) {
            int tmp = findRoot(root, num);
            int size = map.getOrDefault(tmp, 0) + 1;
            map.put(tmp, size);
            maxSize = Math.max(maxSize, size);
        }

        return maxSize;
    }

    private void union(int[] root, int x, int y) {
        int rootX = findRoot(root, x), rootY = findRoot(root, y);
        if (rootX != rootY) {
            root[rootX] = rootY;
        }
    }

    private int findRoot(int[] root, int x) {
        // 路徑壓縮
        return root[x] == x ? x : (root[x] = findRoot(root, root[x]));
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144280.html

標籤：其他

上一篇：云等保有什么用？整改原來還可以這樣操作

下一篇：【資料結構】2.線性表及其結構

0952. Largest Component Size by Common Factor (H)

Largest Component Size by Common Factor (H)

題目

題意

思路

代碼實作

Java