当前位置:网站首页>【952. Calculate the maximum component size according to the common factor】
【952. Calculate the maximum component size according to the common factor】
2022-07-31 00:50:00 【[email protected]】
来源:力扣(LeetCode)
描述:
给定一个由不同正整数的组成的非空数组 nums
,考虑下面的图:
- 有
nums.length
个节点,按从nums[0]
到nums[nums.length - 1]
标记; - 只有当
nums[i]
和nums[j]
共用一个大于 1 的公因数时,nums[i]
和nums[j]
之间才有一条边.
返回 图中最大连通组件的大小 .
示例 1:
输入:nums = [4,6,15,35]
输出:4
示例 2:
输入:nums = [20,50,9,63]
输出:2
示例 3:
输入:nums = [2,3,6,7,4,12,21,39]
输出:8
提示:
- 1 <= nums.length <= 2 * 104
- 1 <= nums[i] <= 105
- nums 中所有值都 不同
方法:并查集
代码:
class UnionFind {
public:
UnionFind(int n) {
parent = vector<int>(n);
rank = vector<int>(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
void uni(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx]++;
}
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
private:
vector<int> parent;
vector<int> rank;
};
class Solution {
public:
int largestComponentSize(vector<int>& nums) {
int m = *max_element(nums.begin(), nums.end());
UnionFind uf(m + 1);
for (int num : nums) {
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
uf.uni(num, i);
uf.uni(num, num / i);
}
}
}
vector<int> counts(m + 1);
int ans = 0;
for (int num : nums) {
int root = uf.find(num);
counts[root]++;
ans = max(ans, counts[root]);
}
return ans;
}
};
执行用时:196 ms, 在所有 C++ 提交中击败了71.01%的用户
内存消耗:75.2 MB, 在所有 C++ 提交中击败了27.54%的用户
author:LeetCode-Solution
版权声明
本文为[[email protected]]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/212/202207310039478432.html
边栏推荐
- What is Promise?What is the principle of Promise?How to use Promises?
- Artificial Intelligence and Cloud Security
- unity2D横版游戏教程4-物品收集以及物理材质
- MySQL grant statements
- MySQL数据库约束,表的设计
- SWM32 Series Tutorial 6 - Systick and PWM
- MySQL database constraints, table design
- Error occurred while trying to proxy request The project suddenly can't get up
- Shell programming of conditional statements
- 牛客网刷题训练(四)
猜你喜欢
ShardingSphere's public table combat (7)
WMware Tools installation failed segmentation fault solution
DOM系列之scroll系列
The difference between h264 and h265 decoding
typescript12 - union types
typescript10-commonly used basic types
场景之多数据源查询及数据下载问题
什么是Promise?Promise的原理是什么?Promise怎么用?
Go study notes (84) - Go project directory structure
ECCV 2022丨轻量级模型架构火了,力压苹果MobileViT(附代码和论文下载)
随机推荐
MySQL数据库面试题总结(2022最新版)
registers (assembly language)
SWM32 Series Tutorial 6 - Systick and PWM
C language force buckles the rotating image of the 48th question.auxiliary array
[Tang Yudi Deep Learning-3D Point Cloud Combat Series] Study Notes
typescript15-(同时指定参数和返回值类型)
MySQL数据库(基础)
MySQL triggers
场景之多数据源查询及数据下载问题
mysql索引失效的常见9种原因详解
typescript10-commonly used basic types
WEB Security Basics - - - Vulnerability Scanner
GO GOPROXY proxy Settings
MySQL master-slave replication and read-write separation script - pro test available
【多线程】
【愚公系列】2022年07月 Go教学课程 016-运算符之逻辑运算符和其他运算符
【Multithreading】
Rocky/GNU之Zabbix部署(2)
什么是Promise?Promise的原理是什么?Promise怎么用?
ABC 261 F - Sorting Color Balls (reverse pair)