type
status
date
slug
summary
tags
category
icon
password
‣
按公因数计算最大组件大小
给定一个由不同正整数的组成的非空数组
nums
,考虑下面的图:- 有
nums.length
个节点,按从nums[0]
到nums[nums.length - 1]
标记;
- 只有当
nums[i]
和nums[j]
共用一个大于 1 的公因数时,nums[i]
和nums[j]
之间才有一条边。
返回 图中最大连通组件的大小 。
示例 1:
示例 2:
示例 3:
提示:
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 105
nums
中所有值都 不同
题解
并查集
为了得到数组 nums 中的每个数和哪些数属于同一个组件,需要得到数组 nums 中的最大值 m,对于每个不超过 m 的正整数 num 计算 num 和哪些数属于同一个组件。对于范围 [2,] 内的每个正整数 i,如果 i 是 num 的因数,则 num 和 i、num/i都属于同一个组件。
可以使用并查集实现组件的计算。初始时,每个数分别属于不同的组件。如果两个正整数满足其中一个正整数是另一个正整数的因数,则这两个正整数属于同一个组件,将这两个正整数的组件合并。
当所有不超过 m 的正整数都完成合并操作之后。遍历数组 nums,对于每个数得到其所在的组件并更新该组件的大小,遍历结束之后即可得到最大组件的大小。
- Author:Zinphy
- URL:https://zouysay.cn/article/algorithm/union
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!