如何高效将整数数组拆分为质因子无重叠的子数组

你这个场景最适合用并查集（Disjoint Set Union, DSU） 数据结构解决，合并操作的时间复杂度可以降低到近似常数，整体复杂度远低于原有的O(n²)方案。
核心逻辑：

• 把数组元素和它的所有质因子都视为并查集中的独立节点
• 对每个元素，将它和自身的所有质因子执行合并操作
• 最终所有连通分量里的元素就是符合要求的子数组：共享质因子的元素会被归入同一个连通分量，不同连通分量之间没有公共质因子

先指出你原有实现的两个明显缺陷：

1. calculatePrimeFactors方法最后integersPrimesMap.put(n, factors)里的n已经是质因子分解后剩余的值，不是原始输入的元素值，会导致映射关系完全错误，比如输入元素是6，分解完n变为1，最终存入的key是1而非6
2. 嵌套循环合并集合的逻辑不仅时间复杂度高，还存在并发修改风险，n规模超过1000之后性能会急剧下降

import java.util.*;

public class SOExample {
    // 哈希表实现并查集，支持大数值的质因子/元素存储
    static class DSU {
        private final Map<Integer, Integer> parent = new HashMap<>();
        private final Map<Integer, Integer> rank = new HashMap<>();

        public int find(int x) {
            if (!parent.containsKey(x)) {
                parent.put(x, x);
                rank.put(x, 1);
            }
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x))); // 路径压缩
            }
            return parent.get(x);
        }

        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx == fy) return;
            // 按秩合并
            if (rank.get(fx) < rank.get(fy)) {
                parent.put(fx, fy);
            } else {
                parent.put(fy, fx);
                if (rank.get(fx).equals(rank.get(fy))) {
                    rank.put(fx, rank.get(fx) + 1);
                }
            }
        }
    }

    public List<List<Integer>> splitArray(int[] arr) {
        DSU dsu = new DSU();
        Map<Integer, Set<Integer>> numToPrimes = new HashMap<>();

        // 第一步：计算每个元素的质因子，同时合并元素和质因子
        for (int num : arr) {
            if (numToPrimes.containsKey(num)) continue;
            Set<Integer> primes = getPrimeFactors(num);
            numToPrimes.put(num, primes);
            // 把元素和所有质因子合并
            for (int p : primes) {
                dsu.union(num, p);
            }
        }

        // 第二步：按根分组，生成结果子数组
        Map<Integer, List<Integer>> rootToSubarray = new HashMap<>();
        for (int num : arr) {
            int root = dsu.find(num);
            rootToSubarray.computeIfAbsent(root, k -> new ArrayList<>()).add(num);
        }

        return new ArrayList<>(rootToSubarray.values());
    }

    // 质因子分解逻辑，修复了原实现的key错误问题
    private Set<Integer> getPrimeFactors(int n) {
        Set<Integer> factors = new HashSet<>();
        if (n % 2 == 0) {
            factors.add(2);
            while (n % 2 == 0) {
                n /= 2;
            }
        }
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                factors.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 2) {
            factors.add(n);
        }
        return factors;
    }

    // 测试用例
    public static void main(String[] args) {
        SOExample example = new SOExample();
        int[] arr = {2,3,6,7,9,14,19};
        List<List<Integer>> result = example.splitArray(arr);
        System.out.println(result); // 输出[[2, 3, 6, 7, 9, 14], [19]] 符合预期
    }
}

• 质因子分解阶段：时间复杂度为O(n * sqrt(max(arr)))，n为数组长度，max(arr)是数组里的最大元素值
• 并查集操作阶段：所有union和find操作的均摊时间复杂度近似为O(1)
• 整体复杂度远低于原有O(n²)的合并方案，n越大性能优势越明显

内容的提问来源于stack exchange，提问作者Kamil12