mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
57 lines
2.2 KiB
Markdown
Executable File
57 lines
2.2 KiB
Markdown
Executable File
# [952. Largest Component Size by Common Factor](https://leetcode.com/problems/largest-component-size-by-common-factor/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given a non-empty array of unique positive integers `A`, consider the following graph:
|
||
|
||
- There are `A.length` nodes, labelled `A[0]` to `A[A.length - 1];`
|
||
- There is an edge between `A[i]` and `A[j]` if and only if `A[i]`and `A[j]` share a common factor greater than 1.
|
||
|
||
Return the size of the largest connected component in the graph.
|
||
|
||
**Example 1:**
|
||
|
||
Input: [4,6,15,35]
|
||
Output: 4
|
||
|
||
|
||
|
||
**Example 2:**
|
||
|
||
Input: [20,50,9,63]
|
||
Output: 2
|
||
|
||
|
||
|
||
**Example 3:**
|
||
|
||
Input: [2,3,6,7,4,12,21,39]
|
||
Output: 8
|
||
|
||
|
||
|
||
**Note:**
|
||
|
||
1. `1 <= A.length <= 20000`
|
||
2. `1 <= A[i] <= 100000`
|
||
|
||
|
||
## 题目大意
|
||
|
||
给定一个由不同正整数的组成的非空数组 A，考虑下面的图：
|
||
|
||
有 A.length 个节点，按从 A[0] 到 A[A.length - 1] 标记；
|
||
只有当 A[i] 和 A[j] 共用一个大于 1 的公因数时，A[i] 和 A[j] 之间才有一条边。
|
||
返回图中最大连通组件的大小。
|
||
|
||
提示：
|
||
|
||
1. 1 <= A.length <= 20000
|
||
2. 1 <= A[i] <= 100000
|
||
|
||
## 解题思路
|
||
|
||
- 给出一个数组，数组中的元素如果每两个元素有公约数，那么这两个元素可以算有关系。所有有关系的数可以放在一个集合里，问这个数组里面有关系的元素组成的集合里面最多有多少个元素。
|
||
- 这一题读完题直觉就是用并查集来解题。首先可以用暴力的解法尝试。用 2 层循环，两两比较有没有公约数，如果有公约数就 `union()` 到一起。提交以后出现 TLE，其实看一下数据规模就知道会超时，`1 <= A.length <= 20000`。注意到 `1 <= A[i] <= 100000`，开根号以后最后才 316.66666，这个规模的数不大。所以把每个数小于根号自己的因子都找出来，例如 `6 = 2 * 3`，`15 = 3 * 5`，那么把 6 和 2，6 和 3 都 `union()`，15 和 3，15 和 5 都 `union()`，最终遍历所有的集合，找到最多元素的集合，输出它包含的元素值。
|