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

Difficulty
Hard
Tags
并查集
URL
https://leetcode.cn/problems/largest-component-size-by-common-factor/
Star
给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：
  • 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
  • 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
返回 图中最大连通组件的大小 。
示例 1：
输入：nums = [4,6,15,35]
输出：4
示例 2：
输入：nums = [20,50,9,63]
输出：2
示例 3：
notion imagenotion image
输入：nums = [2,3,6,7,4,12,21,39]
输出：8
提示：
  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 105
  • nums 中所有值都 不同

并查集

思路
求出每个数字的因数，然后用hash map 来存放 某个因数 的数字。例如数字 8，则有 hashmap[2] = [8] hashmap[4] = [8], 因为 8 有两个因数 2 4 ，都要存放数字 8
存好之后，用 union find 建图 ，同时 size 维护最大的两桶分量。
题解
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        r_x = self.find(x)
        r_y = self.find(y)
        if r_x != r_y:
            if self.size[r_x] > self.size[r_y]:
                self.root[r_y] = r_x
                self.size[r_x] += self.size[r_y]
            else:
                self.root[r_x] = r_y
                self.size[r_y] += self.size[r_x]

    
class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        hash_map = collections.defaultdict(list)
        
        # 分解质因数
        for i in range(0, len(nums)):
            cur = nums[i]
            factor = 2
            while factor * factor <= cur:
                if cur % factor == 0:
                    hash_map[factor].append(i)
                    while cur % factor == 0:
                        cur = cur // factor
                factor += 1
                
            if cur > 1:
                hash_map[cur].append(i)

        # 并查集 构建联通图
        uf = UnionFind(len(nums))
        for f, values in hash_map.items():
            for i in range(0, len(values)-1):
                uf.union(values[i], values[i+1])

        return max(uf.size)