这是 LeetCode 上的 952. 按公因数计算最大组件大小 ,难度为 困难。
Tag : 「数学」、「并查集」
给定一个由不同正整数的组成的非空数组 nums,考虑下面的图:
返回 图中最大连通组件的大小 。
示例 1:
输入:nums = [4,6,15,35]
输出:4
示例 2:
输入:nums = [20,50,9,63]
输出:2
示例 3:
输入:nums = [2,3,6,7,4,12,21,39]
输出:8
提示:
先考虑如何使用 nums 进行建图,nums 大小为 n=2×104n = 2 imes 10^4n=2×104,枚举所有点对并通过判断两数之间是否存在边的做法复杂度为 O(n2M)O(n^2sqrt{M})O(n2M)(其中 M=1e5M = 1e5M=1e5 为 nums[i]nums[i]nums[i] 的最大值),无须考虑。
而不通过「枚举点 + 求公约数」的建图方式,可以对 nums[i]nums[i]nums[i] 进行质因数分解(复杂度为 O(nums[i])O(sqrt{nums[i]})O(nums[i])),假设其分解出来的质因数集合为 SSS,我们可以建立从 SkS_{k}Sk 到 nums[i]nums[i]nums[i] 的映射关系,若 nums[i]nums[i]nums[i] 与 nums[j]nums[j]nums[j] 存在边,则 nums[i]nums[i]nums[i] 和 nums[j]nums[j]nums[j] 至少会被同一个质因数所映射。
维护连通块数量可以使用「并查集」来做,维护映射关系可以使用「哈希表」来做。
维护映射关系时,使用质因数为 key,下标值 iii 为 value(我们使用下标 iii 作为点编号,而不是使用 nums[i]nums[i]nums[i] ,是利用nums[i]nums[i]nums[i] 各不相同,从而将并查集数组大小从 1e51e51e5 收窄到 2×1042 imes 10^42×104)。
同时在使用「并查集」维护连通块时,同步维护每个连通块大小 sz 以及当前最大的连通块大小 ans。
Java 代码:
class Solution {
static int N = 20010;
static int[] p = new int[N], sz = new int[N];
int ans = 1;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int a, int b) {
if (find(a) == find(b)) return ;
sz[find(a)] += sz[find(b)];
p[find(b)] = p[find(a)];
ans = Math.max(ans, sz[find(a)]);
}
public int largestComponentSize(int[] nums) {
int n = nums.length;
Map> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int cur = nums[i];
for (int j = 2; j * j <= cur; j++) {
if (cur % j == 0) add(map, j, i);
while (cur % j == 0) cur /= j;
}
if (cur > 1) add(map, cur, i);
}
for (int i = 0; i <= n; i++) {
p[i] = i; sz[i] = 1;
}
for (int key : map.keySet()) {
List list = map.get(key);
for (int i = 1; i < list.size(); i++) union(list.get(0), list.get(i));
}
return ans;
}
void add(Map> map, int key, int val) {
List list = map.getOrDefault(key, new ArrayList<>());
list.add(val);
map.put(key, list);
}
}
TypeScript 代码:
const N = 20010
const p: number[] = new Array(N), sz = new Array(N)
let ans = 0
function find(x: number): number {
if (p[x] != x) p[x] = find(p[x])
return p[x]
}
function union(a: number, b: number): void {
if (find(a) == find(b)) return
sz[find(a)] += sz[find(b)]
p[find(b)] = p[find(a)]
ans = Math.max(ans, sz[find(a)])
}
function largestComponentSize(nums: number[]): number {
const n = nums.length
const map: Map> = new Map>()
for (let i = 0; i < n; i++) {
let cur = nums[i]
for (let j = 2; j * j <= cur; j++) {
if (cur % j == 0) add(map, j, i)
while (cur % j == 0) cur /= j
}
if (cur > 1) add(map, cur, i)
}
for (let i = 0; i < n; i++) {
p[i] = i; sz[i] = 1
}
ans = 1
for (const key of map.keys()) {
const list = map.get(key)
for (let i = 1; i < list.length; i++) union(list[0], list[i])
}
return ans
};
function add(map: Map>, key: number, val: number): void {
let list = map.get(key)
if (list == null) list = new Array()
list.push(val)
map.set(key, list)
}
链接:https://juejin.cn/post/7214855127626104869
页面更新:2024-04-11
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号