豆包 LeetCode 1998.数组的最大公因数排序 Go实现

LeetCode 1998 数组的最大公因数排序 Go 实现思路并查集 最小质因子筛1. 先找出数组最大值预处理最小质因子2. 把每个数与其所有质因子并入同一集合3. 数组排序后逐个位置检查原数和排序后同位置数是否在同一连通集不在则返回 falseGo 完整代码gopackage mainimport (sort)// 并查集type DSU struct {parent []int}func NewDSU(n int) *DSU {parent : make([]int, n1)for i : range parent {parent[i] i}return DSU{parent: parent}}func (d *DSU) Find(x int) int {if d.parent[x] ! x {d.parent[x] d.Find(d.parent[x])}return d.parent[x]}func (d *DSU) Union(x, y int) {fx : d.Find(x)fy : d.Find(y)if fx ! fy {d.parent[fy] fx}}func gcdSort(nums []int) bool {maxVal : 0for _, v : range nums {if v maxVal {maxVal v}}// 最小质因子筛minPrime : make([]int, maxVal1)for i : 2; i maxVal; i {if minPrime[i] 0 {minPrime[i] ifor j : i * i; j maxVal; j i {if minPrime[j] 0 {minPrime[j] i}}}}dsu : NewDSU(maxVal)// 每个数和质因子合并for _, num : range nums {cur : numpre : -1for cur 1 {p : minPrime[cur]if p ! pre {dsu.Union(num, p)pre p}for cur%p 0 {cur / p}}}// 拷贝并排序sorted : make([]int, len(nums))copy(sorted, nums)sort.Ints(sorted)// 逐位置校验for i : range nums {if dsu.Find(nums[i]) ! dsu.Find(sorted[i]) {return false}}return true}核心逻辑说明1. 并查集维护数字、质因子的连通关系有公共质因子就可互相交换2. 最小质因子线性筛快速分解每个数的不同质因数3. 校验规则能交换的数必须在同一个连通块排序后同位置元素必须同源直接可提交 LeetCode无需修改。需要我给你加详细注释版吗