豆包 LeetCode 1998.数组的最大公因数排序 public boolean gcdSort(int[] nums)

LeetCode 1998 数组的最大公因数排序

题意

给你一个数组 nums ，可以交换最大公因数 > 1 的两个元素任意多次。
问：能否通过若干次交换，把数组变成非递减有序？

核心思路

1. 连通性建模：若两数 gcd>1，可连通；同一连通分量里的数可以任意互换位置。
2. 并查集 + 质因数关联：- 先预处理每个数的所有质因子
- 把每个数和它的质因子在并查集中合并
- 原数组排序后，逐个位置校验：原数和排序后同位置数是否在同一连通分量，有一个不在就返回 false

Java 完整代码

java
import java.util.*;

public class Solution {
static class DSU {
int[] parent;
public DSU(int n) {
parent = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) parent[fy] = fx;
}
}

public boolean gcdSort(int[] nums) {
int maxVal = 0;
for (int num : nums) maxVal = Math.max(maxVal, num);

DSU dsu = new DSU(maxVal);
// 筛法求最小质因子
int[] minPrime = new int[maxVal + 1];
for (int i = 2; i <= maxVal; i++) {
if (minPrime[i] == 0) {
minPrime[i] = i;
for (long j = (long) i * i; j <= maxVal; j += i) {
if (minPrime[(int) j] == 0) minPrime[(int) j] = i;
}
}
}

// 每个数和它的质因子合并
for (int num : nums) {
int cur = num;
int pre = -1;
while (cur > 1) {
int p = minPrime[cur];
if (p != pre) {
dsu.union(num, p);
pre = p;
}
while (cur % p == 0) cur /= p;
}
}

// 排序数组
int[] sorted = nums.clone();
Arrays.sort(sorted);

// 逐位置校验是否同连通分量
for (int i = 0; i < nums.length; i++) {
if (dsu.find(nums[i]) != dsu.find(sorted[i])) {
return false;
}
}
return true;
}
}


思路拆解

1. 最小质因子筛：快速分解任意数的所有不同质因数。
2. 并查集合并：把数字和它的质因子合并，共享质因子的数字天然连通。
3. 校验合法性：排序后，每个位置原数和排序数必须在同一连通块，否则无法交换到位。

复杂度

- 时间：O(M\log M + N\log N)，M 为数组最大值，N 为数组长度
- 空间：O(M)

需要我给你Python / C++ 版本同题代码，或精简版注释版吗？