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

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

思路

并查集 + 最小质因子筛：

1. 先找出数组最大值，预处理最小质因子
2. 把每个数与其所有质因子并入同一集合
3. 数组排序后，逐个位置检查：原数和排序后同位置数是否在同一连通集，不在则返回 false

Go 完整代码

go
package main

import (
"sort"
)

// 并查集
type DSU struct {
parent []int
}

func NewDSU(n int) *DSU {
parent := make([]int, n+1)
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 := 0
for _, v := range nums {
if v > maxVal {
maxVal = v
}
}

// 最小质因子筛
minPrime := make([]int, maxVal+1)
for i := 2; i <= maxVal; i++ {
if minPrime[i] == 0 {
minPrime[i] = i
for j := i * i; j <= maxVal; j += i {
if minPrime[j] == 0 {
minPrime[j] = i
}
}
}
}

dsu := NewDSU(maxVal)
// 每个数和质因子合并
for _, num := range nums {
cur := num
pre := -1
for 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，无需修改。需要我给你加详细注释版吗？