LeetCode 952. Largest Component Size by Common Factor

Posted on | In |
Words count in article: 220 | Reading time ≈ 1

题目

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:

1
2
Input: [4,6,15,35]
Output: 4

Example 2:

1
2
Input: [20,50,9,63]
Output: 2

Example 3:

1
2
Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

  • 1 <= A.length <= 20000
  • 1 <= A[i] <= 100000

思路

Solution Video.

For each number, union itself with all its factors.

E.g. 6, union(6,2), union(6,3)

Time complexity: $𝑂(Σ𝑠𝑞𝑟𝑡(𝐴[𝑖]))$
Space complexity: $𝑂(𝑚𝑎𝑥(𝐴))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def largestComponentSize(self, A: List[int]) -> int:
        p = list(range(max(A) + 1))
        def find(x):
            while p[x] != x:
                p[x] = p[p[x]]
                x = p[x]
            return x
        
        def union(x, y):
            p[find(x)] = p[find(y)]
        
        for a in A:     
            for k in range(2, int(math.sqrt(a) + 1)):        
                if a % k == 0:
                    union(a, k)
                    union(a, a // k)
        
        return collections.Counter([find(a) for a in A]).most_common(1)[0][1]