Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
952. Largest Component Size by Common Factor.go
952. Largest Component Size by Common Factor_test.go
README.md

README.md

952. 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 * 315 = 3 * 5,那么把 6 和 2,6 和 3 都 union(),15 和 3,15 和 5 都 union(),最终遍历所有的集合,找到最多元素的集合,输出它包含的元素值。
You can’t perform that action at this time.