LeetCode 952. 按公因数计算最大组件大小

952. 按公因数计算最大组件大小

 

【质因数+并查集】一开始我想的是两两用gcd查公因数，如果不是1就用并查集合并，但是复杂度O(n * n * gcd)，O(gcd) = O(logm)，所以显然是超时的。

换种思路，可以求每个数的所有约数，然后以约数为key，以数的list为value存到哈希表中，每次把相同key的list下的数合并到并查集中这样复杂度只有O(n * logm)，另外发现nums各不相同因此可以进行离散化把[1, 10^5]映射到[1, 2 * 10^4]上，也就是list中存数组的下标，并查集中也是合并元素下标。

求质因数可以这么写：

for(i = 2; i * i <= n; i++) {

        if (n * i == 0) i-> yes;

        while (n % i == 0) n /= i;      // 把这个因数除干净

}

if(n != 1) n-> yes;       //最后千万别忘了把最终得到的n加上

class Solution {
public:

    int N = (int)2e4 + 1;
    int *f;
    int *d;
    int ans = 1;

    int ask(int x) {
        return x == f[x]? x: ask(f[x]);
    }

    void merge(int x, int y) {
        x = ask(x);
        y = ask(y);
        if (x == y) return;
        d[x] += d[y];
        f[y] = f[x];
        ans = max(d[x], ans);
    }

    int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        f = (int*)malloc(sizeof(int) * N);
        d = (int*)malloc(sizeof(int) * N);
        unordered_map<int, vector<int>> m;
        for (auto i = 0; i < N; i++) f[i] = i;
        for (auto i = 0; i < N; i++) d[i] = 1;
        for (auto i = 0; i < n; i++) {
            int x = nums[i];
            for (auto j = 2; j * j <= x; j++) {
                if (x % j == 0) m[j].push_back(i);
                while (x % j == 0) x /= j;
            }
            if (x != 1) m[x].push_back(i);
        }
        for (auto & it: m) {
            vector<int> l = it.second;
            int tmp = l.size();
            for (auto i = 1; i < tmp; i++) {
                merge(l[i - 1], l[i]);
            }
        }
        return ans;
    }
};

class Solution {

    // 并查集 10:31 13

    int N = 20001;
    int[] f = new int[N];
    int[] cnt = new int[N];
    int ans = 1;

    int gcd(int a, int b) {
        return a % b == 0? b: gcd(b, a % b);
    }

    int ask(int x) {
        return x == f[x]? x: ask(f[x]); 
    }

    void union(int x, int y) {
        x = ask(x); y = ask(y);
        if (x == y) return;
        cnt[x] += cnt[y];
        f[y] = x;
        ans = Math.max(ans, cnt[x]);
    }

    public int largestComponentSize(int[] nums) {
        for (var i = 0; i < N; i++) f[i] = i;
        Arrays.fill(cnt, 1);
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (var i = 0; i < n; ++i) {
            var x = nums[i];
            for (var j = 2; j * j <= x; j++) {
                if (x % j == 0) {
                    map.computeIfAbsent(j, k -> new ArrayList()).add(i);
                }
                while (x % j == 0) x /= j;
            }
            if (x != 1)
            map.computeIfAbsent(x, k -> new ArrayList()).add(i);
        }
        for (var k: map.keySet()) {
            var list = map.get(k);
            int m = list.size();
            for (var i = 1; i < m; i++) {
                union(list.get(i - 1), list.get(i));
            }
        }
        return ans;
    }
}