当前位置:网站首页>LeetCode·Daily Question·952. Calculate Maximum Component Size by Common Factor·Union Check
LeetCode·Daily Question·952. Calculate Maximum Component Size by Common Factor·Union Check
2022-07-30 21:17:00 【Xiao Xun wants to become stronger】
Title
Example
Thoughts
Idea:
Elements are connected to each other by a common factor between them.
1. And search:
There is no need to merge by collection size when building, it can be merged directly.The largest connected component can be found by traversing the union search set once.
Works with path compression.See find function.
2. Common factor:
Note that i * i <= num in the loop, if the data range is larger, it may overflow.Better to use i <= num / i .
For example:
nums = [4 , 6 , 12, 15]
where the factor of each number num in nums greater than 2 is:
4 -> 2
6 -> 2, 3
12 -> 2, 3, 4, 6
15 -> 3, 5
When creating and checking the set, the factor 2 can be used to convert 4, 6, 12 are connected.
6, 12, 15 can be connected by a factor of 3.
And factor 2 and factor 3 are also connected (eg 2 is the parent of 3).
Then the four numbers in the original array are connected.It has the same parent node in the union.
Solve
Finally, the array is traversed once, if its parent node is the same, it is in the same connected component.
Just update the maximum number of occurrences of each parent node.
Code
#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;}
Time and space complexity
边栏推荐
猜你喜欢
Use the map function to operate on each element in the list It seems that you don't need a map
大家都在用的plm项目管理软件有哪些
Activiti 工作流引擎 详解
2021年软件测试面试题大全
ENS emoji domain name is on fire!Hype or opportunity?
Enhancing Quality for HEVC Compressed Videos
DPW-SDNet: Dual Pixel-Wavelet Domain Deep CNNs for Soft Decoding of JPEG-Compressed Images
面试难题:分布式 Session 实现难点,这篇就够!
【深度学习】对迁移学习中域适应的理解和3种技术的介绍
mysql deadlock
随机推荐
How strict Typescript strict mode?
微信读书,导出笔记
vlan简单实验
【软件工程之美 - 专栏笔记】31 | 软件测试要为产品质量负责吗?
为什么那么多自学软件测试的人,后来都放弃了...
MySQL BIGINT 数据类型
mpls简介
[Limited Time Bonus] 21-Day Learning Challenge - MySQL from entry to mastery
c语言:操作符详解
How to make a deb package
Motion Tuned Spatio-temporal Quality Assessmentof Natural Videos
mysql deadlock
转义字符笔记记录
LeetCode · 23. Merge K ascending linked lists · recursion · iteration
手把手教你搭建一台永久运行的个人服务器
JDBC (detailed explanation)
走进Redis,让你重新认识redis。绝不是表面
弹性盒子模型
QUALITY-GATED CONVOLUTIONAL LSTM FOR ENHANCING COMPRESSED VIDEO
WeChat reading, export notes