当前位置:网站首页>LeetCode 0952. Calculate Maximum Component Size by Common Factor: Mapping / Union Search
LeetCode 0952. Calculate Maximum Component Size by Common Factor: Mapping / Union Search
2022-07-30 19:21:00 【Tisfy】
【LetMeFly】952.按公因数计算最大组件大小:建图 / 并查集
力扣题目链接:https://leetcode.cn/problems/largest-component-size-by-common-factor/
给定一个由不同正整数的组成的非空数组 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
中所有值都 不同
方法一:建图 + 广搜
First factor each number in the array,用hasThisFactor[i]
There are factors in the storage arrayi
的数,用num4Factor[i]
存放数组中的元素i
的所有的因数.
vector<vector<int>> hasThisFactor(100010);
vector<vector<int>> num4Factor(100010);
for (int t : nums) {
int k = sqrt(t);
for (int i = 2; i <= k; i++) {
if (t % i == 0) {
hasThisFactor[i].push_back(t);
num4Factor[t].push_back(i);
if (t / i != i) {
hasThisFactor[t / i].push_back(t);
num4Factor[t].push_back(t / i);
}
}
}
// oneself is one's own factor
hasThisFactor[t].push_back(t);
num4Factor[t].push_back(t);
}
之后,Iterate over every possible factor,and start searching
During the search process,Record each factor/Whether each element has been searched
If it traverses to an unsearched factor,Take this factor as a starting point,Start to search and build maps.
Extend by all numbers with this factor( j = h a s T h i s F a c t o r [ i ] j = hasThisFactor[i] j=hasThisFactor[i])的所有的因数( n u m 4 F a c t o r [ j ] num4Factor[j] num4Factor[j])
// 开始建图
int ans = 0;
vector<bool> visitedFactor(100010, false); // 标记是否遍历过
vector<bool> visitedNum(100010, false);
for (int i = 2; i <= 100000; i++) {
// Iterate over all possible factors
if (hasThisFactor[i].size() && !visitedFactor[i]) {
// 有 elements with this factor && has not been traversed
visitedFactor[i] = true; // Then this has been traversed
int thisAns = 0; // Start building the graph from this node,Initially, the number of elements in the graph is 0
queue<int> q; // 广搜队列
q.push(i);
while (q.size()) {
int thisFactor = q.front(); // Take out a factor
q.pop();
for (int thisNum : hasThisFactor[thisFactor]) {
// Iterate over all elements with this factor
if (!visitedNum[thisNum]) {
// A new untraversed element
visitedNum[thisNum] = true; // 标记为遍历过
thisAns++; // The number of elements in the graph++
for (int thisNewFactor : num4Factor[thisNum]) {
// Iterate over all factors of this element(can be connected to a graph)
if (!visitedFactor[thisNewFactor]) {
// Untraversed factors
visitedFactor[thisNewFactor] = true; // 标记为遍历过
q.push(thisNewFactor); // 入队
}
}
}
}
}
ans = max(ans, thisAns); // Update answer max
}
}
return ans;
- 时间复杂度 O ( N × M ) O(N\times \sqrt{M}) O(N×M),其中 N N N是数组中元素的个数, M M Mis the maximum value of elements in the array(This is not counted in the above algorithm N N N个元素的最大值,因此按 1 0 5 10^5 105来处理了).遍历过程中,each factor/Elements are only really processed once and traversed several times
- 空间复杂度 O ( N × Q + M ) O(N\times Q + M) O(N×Q+M),其中 Q Q Qis the average number of prime factors of the elements in the array
AC代码
C++
class Solution {
public:
int largestComponentSize(vector<int>& nums) {
// Decomposition factor to hasThisFactor中
vector<vector<int>> hasThisFactor(100010);
vector<vector<int>> num4Factor(100010);
for (int t : nums) {
int k = sqrt(t);
for (int i = 2; i <= k; i++) {
if (t % i == 0) {
hasThisFactor[i].push_back(t);
num4Factor[t].push_back(i);
if (t / i != i) {
hasThisFactor[t / i].push_back(t);
num4Factor[t].push_back(t / i);
}
}
}
// oneself is one's own factor
hasThisFactor[t].push_back(t);
num4Factor[t].push_back(t);
}
// 开始建图
int ans = 0;
vector<bool> visitedFactor(100010, false);
vector<bool> visitedNum(100010, false);
for (int i = 2; i <= 100000; i++) {
if (hasThisFactor[i].size() && !visitedFactor[i]) {
visitedFactor[i] = true;
int thisAns = 0;
queue<int> q;
q.push(i);
while (q.size()) {
int thisFactor = q.front();
q.pop();
for (int thisNum : hasThisFactor[thisFactor]) {
if (!visitedNum[thisNum]) {
visitedNum[thisNum] = true;
thisAns++;
for (int thisNewFactor : num4Factor[thisNum]) {
if (!visitedFactor[thisNewFactor]) {
visitedFactor[thisNewFactor] = true;
q.push(thisNewFactor);
}
}
}
}
}
ans = max(ans, thisAns);
}
}
return ans;
}
};
方法二:并查集
The idea of consolidation is relatively simple,Combine all the factors of each number with the number into a set,Then count how many elements are in each set,Return the maximum number of elements.
Here, the union check class I wrote myself is usedUnionFind
,The maximum number of elements is passed in during construction,合并x
和y
时调用Union(int x, int y)
函数,想得到x
Called when the root of the collection is infind(int x)
function can be easily used.
- 时间复杂度 O ( N × M × α ( N ) ) O(N\times \sqrt{M} \times \alpha(N)) O(N×M×α(N)),其中 N N N是数组中元素的个数, M M Mis the maximum value of elements in the array, α ( N ) \alpha(N) α(N)is the average time complexity of a union-find operation(其中 α \alpha α是反阿克曼函数).
- 空间复杂度 O ( M ) O(M) O(M)
AC代码
C++
class UnionFind {
private:
int* father;
int* rank;
public:
UnionFind(int n) {
father = new int[n];
rank = new int[n];
memset(rank, 0, sizeof(rank));
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
~UnionFind() {
delete[] father;
delete[] rank;
}
int find(int x) {
if (father[x] != x)
father[x] = find(father[x]);
return father[x];
}
void Union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
father[rootY] = rootX;
}
else if (rank[rootX] < rank[rootY]) {
father[rootX] = rootY;
}
else {
father[rootY] = rootX;
rank[rootX]++;
}
}
}
};
class Solution {
public:
int largestComponentSize(vector<int>& nums) {
// And check the build
UnionFind unionFind(*max_element(nums.begin(), nums.end()) + 1);
for (int t : nums) {
int k = sqrt(t);
for (int i = 2; i <= k; i++) {
if (t % i == 0) {
unionFind.Union(i, t);
unionFind.Union(i, t / i);
}
}
}
// Statistics have several sets、How many elements are in each set
unordered_map<int, int> times;
for (int t : nums) {
times[unionFind.find(t)]++;
}
// 统计最大值
int ans = 0;
for (auto[root, appendTime] : times) {
ans = max(ans, appendTime);
}
return ans;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/126069985
边栏推荐
- 牛客刷题系列之进阶版(搜索旋转排序数组,链表内指定区间反转)
- JS提升:Promise中reject与then之间的关系
- Recommendation | People who are kind to you, don't repay them by inviting them to eat
- VBA batch import Excel data into Access database
- VS Code connects to SQL Server
- 浅聊对比学习(Contrastive Learning)第一弹
- Another company interview
- 自己需要努力
- 深入浅出边缘云 | 3. 资源配置
- Witness the magical awakening of the mini world in HUAWEI CLOUD
猜你喜欢
MindSpore:【语音识别】DFCNN网络训练loss不收敛
【Prometheus】Prometheus联邦的一次优化记录[续]
【MindSpore】用coco2017训练Model_zoo上的 yolov4,迭代了两千多batch_size之后报错,大佬们帮忙看看。
OneFlow source code analysis: Op, Kernel and interpreter
Basic use of scrapy
第十七届“振兴杯”全国青年 职业技能大赛——计算机程序设计员(云计算平台与运维)参赛回顾与总结
浅聊对比学习(Contrastive Learning)第一弹
Read the "Language Model" in one article
Swiper轮播图片并播放背景音乐
Recommendation | People who are kind to you, don't repay them by inviting them to eat
随机推荐
技术很牛逼,还需要“向上管理”吗?
Swiper rotates pictures and plays background music
Mysql execution principle analysis
【剑指 Offe】剑指 Offer 18. 删除链表的节点
kotlin by lazy
中集世联达飞瞳全球工业人工智能AI领军者,全球顶尖AI核心技术高泛化性高鲁棒性稀疏样本持续学习,工业级高性能成熟AI产品规模应用
MindSpore:【JupyterLab】按照新手教程训练时报错
VBA batch import Excel data into Access database
【科普】无线电波怎样传送信息?
监听开机广播
云数据库和本地数据库有什么区别?
Common linked list problems and their Go implementation
第4章 控制执行流程
Delay queue optimization (2)
Spark学习:编译Spark项目时遇到的报错
MindSpore:Cifar10Dataset‘s num_workers=8, this value is not within the required range of [1, cpu_thr
【刷题篇】计算质数
电脑死机的时候,发生了什么?
看完《二舅》,我更内耗了
来了!东方甄选为龙江农产品直播带货