LeetCode·每日一题·952.按公因数计算最大组件大小·并查集

题目

 

示例

 

思路

思路：
通过元素间的公因数将彼此连接起来。

1.并查集：

构建时无需按集合大小进行合并，可直接合并。最大的连通组件 可通过对并查集一次遍历求得。
配合路径压缩。见find函数。
2.公因数：

注意循环中 i * i <= num, 如果数据范围更大的话，可能会溢出。 用 i <= num / i 更好。

举例例如：
nums = [4 , 6 , 12, 15]
其中nums中 每个数num 的大于2的因数为：
4  ->  2
6  ->  2, 3
12 ->  2, 3, 4, 6
15 ->  3, 5
建立并查集时，通过 因数 2 可将 4, 6, 12连通。
通过 因数3 可将 6, 12, 15 连通。
而因数 2 和因数 3 也是连通的（如2 是3 的父节点）。
则 原数组中的 四个数连通。其在并查集中 具有相同的父节点。

求解
最后对数组一次遍历，若其父节点相同，则在同一个连通组件中。
更新每个父节点出现的最大次数即可。

代码

#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef struct UnionFind {
    int *parent;
    int *rank;
} UnionFind;

UnionFind* unionFindCreate(int n) {
    UnionFind *obj = (UnionFind *)malloc(sizeof(UnionFind));
    obj->parent = (int *)malloc(sizeof(int) * n);
    obj->rank = (int *)malloc(sizeof(int) * n);
    memset(obj->rank, 0, sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        obj->parent[i] = i;
    }
    return obj;
}

int find(const UnionFind *obj, int x) {
    if (obj->parent[x] != x) {
        obj->parent[x] = find(obj, obj->parent[x]);
    }
    return obj->parent[x];
}

void uni(UnionFind *obj, int x, int y) {
    int rootx = find(obj, x);
    int rooty = find(obj, y);
    if (rootx != rooty) {
        if (obj->rank[rootx] > obj->rank[rooty]) {
            obj->parent[rooty] = rootx;
        } else if (obj->rank[rootx] < obj->rank[rooty]) {
            obj->parent[rootx] = rooty;
        } else {
            obj->parent[rooty] = rootx;
            obj->rank[rootx]++;
        }
    }
}

void unionFindFree(UnionFind *obj) {
    free(obj->parent);
    free(obj->rank);
    free(obj);
}

int largestComponentSize(int* nums, int numsSize) {
    int m = nums[0];
    for (int i = 0; i < numsSize; i++) {
        m = MAX(m, nums[i]);
    }
    UnionFind *uf = unionFindCreate(m + 1);
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                uni(uf, num, i);
                uni(uf, num, num / i);
            }
        }
    }
    int *counts = (int *)malloc(sizeof(int) * (m + 1));
    memset(counts, 0, sizeof(int) * (m + 1));
    int ans = 0;
    for (int i = 0; i < numsSize; i++) {
        int root = find(uf, nums[i]);
        counts[root]++;
        ans = MAX(ans, counts[root]);
    }
    free(counts);
    unionFindFree(uf);
    return ans;
}

时间空间复杂度