largest-component-size-by-common-factor

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array of unique positive integers <code>nums</code>. Consider the following graph:

<ul>
	<li>There are <code>nums.length</code> nodes, labeled <code>nums[0]</code> to <code>nums[nums.length - 1]</code>,</li>
	<li>There is an undirected edge between <code>nums[i]</code> and <code>nums[j]</code> if <code>nums[i]</code> and <code>nums[j]</code> share a common factor greater than <code>1</code>.</li>
</ul>

Return the size of the largest connected component in the graph.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex1.png" style="width: 500px; height: 97px;" />
<pre>
Input: nums = [4,6,15,35]
Output: 4
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex2.png" style="width: 500px; height: 85px;" />
<pre>
Input: nums = [20,50,9,63]
Output: 2
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex3.png" style="width: 500px; height: 260px;" />
<pre>
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 104</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
	<li>All the values of <code>nums</code> are unique.</li>
</ul>

第 113 场周赛

weekly-contest-113

largestComponentSize

首席工程师

Largest Component Size by Common Factor

Groups of Strings

groups-of-strings

字符串分组

Distinct Prime Factors of Product of Array

distinct-prime-factors-of-product-of-array

数组乘积中的不同质因数数目

Union Find

Array

Hash Table

Math

Number Theory

质因数分解

给定一个由不同正整数的组成的非空数组&nbsp;<code>nums</code> ，考虑下面的图：

<ul>
	<li>有&nbsp;<code>nums.length</code>&nbsp;个节点，按从&nbsp;<code>nums[0]</code>&nbsp;到&nbsp;<code>nums[nums.length - 1]</code>&nbsp;标记；</li>
	<li>只有当&nbsp;<code>nums[i]</code>&nbsp;和&nbsp;<code>nums[j]</code>&nbsp;共用一个大于 1 的公因数时，<code>nums[i]</code>&nbsp;和&nbsp;<code>nums[j]</code>之间才有一条边。</li>
</ul>

返回 图中最大连通组件的大小 。

&nbsp;

<ol>
</ol>

示例 1：

<img src="https://assets.leetcode.com/uploads/2018/12/01/ex1.png" style="height: 97px; width: 500px;" />

<pre>
输入：nums = [4,6,15,35]
输出：4
</pre>

示例 2：

<img src="https://assets.leetcode.com/uploads/2018/12/01/ex2.png" style="height: 85px; width: 500px;" />

<pre>
输入：nums = [20,50,9,63]
输出：2
</pre>

示例 3：

<img src="https://assets.leetcode.com/uploads/2018/12/01/ex3.png" style="height: 260px; width: 500px;" />

<pre>
输入：nums = [2,3,6,7,4,12,21,39]
输出：8
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 104</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
	<li><code>nums</code>&nbsp;中所有值都 不同</li>
</ul>

按公因数计算最大组件大小

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：

 * 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
 * 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。

返回 图中最大连通组件的大小 。

 

示例 1：

[https://assets.leetcode.com/uploads/2018/12/01/ex1.png]


输入：nums = [4,6,15,35]
输出：4


示例 2：

[https://assets.leetcode.com/uploads/2018/12/01/ex2.png]


输入：nums = [20,50,9,63]
输出：2


示例 3：

[https://assets.leetcode.com/uploads/2018/12/01/ex3.png]


输入：nums = [2,3,6,7,4,12,21,39]
输出：8


 

提示：

 * 1 <= nums.length <= 2 * 104
 * 1 <= nums[i] <= 105
 * nums 中所有值都 不同