当前位置:网站首页>LeetCode 0952.按公因数计算最大组件大小:建图 / 并查集
LeetCode 0952.按公因数计算最大组件大小:建图 / 并查集
2022-07-30 19:16: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
中所有值都 不同
方法一:建图 + 广搜
首先将数组中的每个数分解因数,用hasThisFactor[i]
存放数组中有因素i
的数,用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);
}
}
}
// 自己是自己的因数
hasThisFactor[t].push_back(t);
num4Factor[t].push_back(t);
}
之后,遍历每一个可能的因数,并开始广搜
广搜过程中,记录每一个因数/每一个元素是否被搜索过
如果遍历到了一个未被搜索过的因数,就以此因数为起点,开始广搜建图。
拓展依据所有拥有这个因数的数( 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++) {
// 遍历所有可能的因数
if (hasThisFactor[i].size() && !visitedFactor[i]) {
// 有 有这个因数的元素 && 未被遍历过
visitedFactor[i] = true; // 那么这就遍历过了
int thisAns = 0; // 从这个节点开始建图,初始时图中元素个数为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;
- 时间复杂度 O ( N × M ) O(N\times \sqrt{M}) O(N×M),其中 N N N是数组中元素的个数, M M M是数组中元素的最大值(上述算法中没有统计这 N N N个元素的最大值,因此按 1 0 5 10^5 105来处理了)。遍历过程中,每个因数/元素只会被真正地处理一次和被遍历数次
- 空间复杂度 O ( N × Q + M ) O(N\times Q + M) O(N×Q+M),其中 Q Q Q是数组中元素的平均质因数的个数
AC代码
C++
class Solution {
public:
int largestComponentSize(vector<int>& nums) {
// 分解因数到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);
}
}
}
// 自己是自己的因数
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;
}
};
方法二:并查集
并查集的思路较为简单,把每个数的所有因数和这个数合并到一个集合中,然后统计每个集合中有多少个元素,返回最大的元素个数即可。
这里用到了自己写的并查集类UnionFind
,构造时传入最大元素个数,合并x
和y
时调用Union(int x, int y)
函数,想得到x
所在集合的根时调用find(int x)
函数即可很方便地使用。
- 时间复杂度 O ( N × M × α ( N ) ) O(N\times \sqrt{M} \times \alpha(N)) O(N×M×α(N)),其中 N N N是数组中元素的个数, M M M是数组中元素的最大值, α ( N ) \alpha(N) α(N)是平均一次并查集操作的时间复杂度(其中 α \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) {
// 并查集构建
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);
}
}
}
// 统计有几个集合、每个集合中有多少个元素
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
边栏推荐
猜你喜欢
Win11如何更改默认下载路径?Win11更改默认下载路径的方法
牛客刷题系列之进阶版(组队竞赛,排序子序列,倒置字符串, 删除公共字符,修理牧场)
The advanced version of the Niu Ke brushing series (team competition, sorting subsequences, inverting strings, deleting common characters, repairing pastures)
The use of @ symbol in MySql
CIMC Shilian Dafeitong is the global industrial artificial intelligence AI leader, the world's top AI core technology, high generalization, high robustness, sparse sample continuous learning, industri
SimpleOSS第三方库libcurl与引擎libcurl错误解决方法
MindSpore:ImageFolderDataset数据读取问题
SwiftUI iOS Boutique Open Source Project Complete Baked Food Recipe App based on SQLite (tutorial including source code)
Critical Reviews | A review of the global distribution of antibiotics and resistance genes in farmland soil by Nannong Zou Jianwen's group
Does the satellite phone communicate directly with the satellite or through a ground station?
随机推荐
Difference between Object and Map
MYSQL (Basic) - An article takes you into the wonderful world of MYSQL
几个GTest、GMock的例子
Read the "Language Model" in one article
【Swords Offer】Swords Offer 17. Print n digits from 1 to the largest
6块钱1斤,日本公司为何来中国收烟头?
[Prometheus] An optimization record of the Prometheus federation [continued]
卫星电话是直接与卫星通信还是通过地面站?
运营 23 年,昔日“国内第一大电商网站”黄了...
中集世联达工业级成熟航运港口人工智能AI产品规模化应用,打造新一代高效能智慧港口和创新数字港口,全球港航人工智能能领军者中集飞瞳
Critical Reviews | A review of the global distribution of antibiotics and resistance genes in farmland soil by Nannong Zou Jianwen's group
Go system collection
实体中增加操作方法
还有三天忙完
2种手绘风格效果比较,你更喜欢哪一种呢?
requet.getHeader("token") is null
JsonUtil基于字符串操作josn
解决终极bug,项目最终能顺利部署上线。
已删除
OneFlow源码解析:Op、Kernel与解释器