当前位置:网站首页>【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
边栏推荐
- MySQL筑基篇之增删改查
- MySQL triggers
- Common network status codes
- Detailed explanation of 9 common reasons for MySQL index failure
- unity2D横版游戏教程4-物品收集以及物理材质
- BOM系列之Navigator对象
- MySql数据恢复方法个人总结
- WMware Tools installation failed segmentation fault solution
- typescript15-(同时指定参数和返回值类型)
- Oracle has a weird temporary table space shortage problem
猜你喜欢
go mode tidy出现报错go warning “all“ matched no packages
Summary of MySQL database interview questions (2022 latest version)
typescript11 - data types
什么是Promise?Promise的原理是什么?Promise怎么用?
ShardingSphere之公共表实战(七)
mysql主从复制及读写分离脚本-亲测可用
ShardingSphere's unsharded table configuration combat (6)
Go 学习笔记(84)— Go 项目目录结构
场景之多数据源查询及数据下载问题
【多线程】
随机推荐
typescript12-联合类型
typescript16-void
程序员工作三年攒多少钱合适?
人工智能与云安全
typescript9 - common base types
【Yugong Series】July 2022 Go Teaching Course 017-IF of Branch Structure
Why use high-defense CDN when financial, government and enterprises are attacked?
Common network status codes
Asser uses ant sword to log in
埃拉托斯特尼筛法
Oracle has a weird temporary table space shortage problem
typescript9-常用基础类型
[Yugong Series] July 2022 Go Teaching Course 016-Logical Operators and Other Operators of Operators
ES 中时间日期类型 “yyyy-MM-dd HHmmss” 的完全避坑指南
A complete guide to avoiding pitfalls for the time-date type "yyyy-MM-dd HHmmss" in ES
牛客网刷题训练(四)
The client series of the DOM series
Rocky/GNU之Zabbix部署(2)
Jmeter参数传递方式(token传递,接口关联等)
Filter (Filter)