当前位置:网站首页>Leetcode952. Calculate maximum component size by common factor
Leetcode952. Calculate maximum component size by common factor
2022-07-31 07:39:00 【hhhcbw】
题目链接
题目大意
比如 nums = [4,6,15,35] 答案就是4,nums = [20,50,9,63] 答案就是2.
解题思路
我的思路是对 nums
Prime factorization of each number in the array,Then a union can be maintained for each factor,For a number, all factors after its prime factorization can be regarded as a connected set.In this way, you can maintain and check the set size online.素数筛+质因子分解+并查集,时间复杂度为 O(mlogn),m为数组大小,n为数字大小.
当然,You can also follow the official solution,Direct use and query set maintenance,Every number and every factor is a connected component,Finally, determine who the father of the current number is,And just update the set size.The official time complexity is O(m n \sqrt{n} n).
代码(C++)
我的代码
const int N = 1e5+5;
class Solution {
public:
//核心:n只会被最小质因子筛掉
int cnt = 0; //素数的个数
int v[N]; //Store the smallest prime factor of each number
int prime[N]; //存素数
int fa[N]; // 并查集父节点
int size[N]; // 并查集大小
void get_primes(int n){
for(int i = 2;i <= n; ++i){
if(v[i] == 0){
v[i] = i;
prime[++cnt] = i;
}
for(int j = 1 ; j <= cnt;++j){
if(prime[j] > v[i] || i * prime[j] > n) break;
v[prime[j] * i] = prime[j];
}
}
}
// void divide(int n) {
// while (v[n]) {
// printf("%d ", v[n]); // 在前
// n /= v[n]; //在后
// }
// }
int find(int x)
{
if(x == fa[x])
return x;
else
return find(fa[x]);
}
int largestComponentSize(vector<int>& nums) {
int ans = 1;
get_primes(100000);
for(int i=0; i<nums.size(); ++i)
{
int father = 0;
while (v[nums[i]])
{
int now = v[nums[i]];
if(father == 0)
{
father = now;
if(fa[father] == 0)
{
fa[father] = father;
size[father] = 1;
}
else
{
size[find(father)] ++;
ans = max(ans, size[find(father)]);
}
}
else
{
if(fa[now] == 0)
{
fa[now] = find(father);
}
else if(find(father) != find(now))
{
size[find(father)] += size[find(now)];
ans = max(size[find(father)], ans);
fa[find(now)] = find(father);
}
}
while (nums[i] % now == 0)
nums[i] /= now;
}
}
return ans;
}
};
官方代码
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;
}
};
边栏推荐
- nohup原理
- Postgresql source code learning (34) - transaction log ⑩ - full page write mechanism
- 【Go语言入门教程】Go语言简介
- Core Tower Electronics won the championship in the Wuhu Division of the 11th China Innovation and Entrepreneurship Competition
- 多进程全局变量失效、变量共享问题
- 深度学习通信领域相关经典论文、数据集整理分享
- 线程中断方法
- 2022.07.18_每日一题
- 基于LSTM的诗词生成
- tidyverse笔记——dplyr包
猜你喜欢
2.(1)栈的链式存储、链栈的操作(图解、注释、代码)
Conditional statements of shell (test, if, case)
2022.07.24_每日一题
【Go语言刷题篇】Go完结篇函数、结构体、接口、错误入门学习
2022.07.14_每日一题
Web浏览器工作流程解析
2. (1) Chained storage of stack, operation of chain stack (illustration, comment, code)
双倍数据速率同步动态随机存储器(Double Data Rate Synchronous Dynamic Random Access Memory, DDR SDRAM)- 逻辑描述部分
[PSQL] SQL基础教程读书笔记(Chapter1-4)
基于LSTM的诗词生成
随机推荐
2022.07.26_每日一题
DAY18:XSS 漏洞
Detailed explanation of js prototype
基于LSTM的诗词生成
金融租赁业务
高并发与多线程之间的难点对比(容易混淆)
【Go报错】go go.mod file not found in current directory or any parent directory 错误解决
批量免费文字翻译
【C语言项目合集】这十个入门必备练手项目,让C语言对你来说不再难学!
Analysis of pseudo-classes and pseudo-elements
‘vite‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件。
Some derivation formulas for machine learning backpropagation
postgresql源码学习(33)—— 事务日志⑨ - 从insert记录看日志写入整体流程
【网络攻防】常见的网络攻防技术——黑客攻防(通俗易懂版)
leetcode 406. Queue Reconstruction by Height
事务的四大特性
文件 - 03 下载文件:根据文件id获取下载链接
Web浏览器工作流程解析
2022.7.29 Array
2022.07.24_每日一题