首页算法

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

难度困难

给你一个整数数组 nums ，你可以在 nums 上执行下述操作 任意次 ：

  • 如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums[i], nums[j]) 是 nums[i] 和 nums[j] 的最大公因数。

如果能使用上述交换方式将 nums 按 非递减顺序 排列，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [7,21,3]

输出：true

解释：可以执行下述操作完成对 [7,21,3] 的排序：

  • 交换 7 和 21 因为 gcd (7,21) = 7 。nums = [21,7,3]
  • 交换 21 和 3 因为 gcd (21,3) = 3 。nums = [3,7,21]

示例 2：

输入：nums = [5,2,6,2]

输出：false

解释：无法完成排序，因为 5 不能与其他元素交换。

示例 3：

输入：nums = [10,5,9,3,15]

输出：true

解释：
可以执行下述操作完成对 [10,5,9,3,15] 的排序：

  • 交换 10 和 15 因为 gcd (10,15) = 5 。nums = [15,5,9,3,10]
  • 交换 15 和 3 因为 gcd (15,3) = 3 。nums = [3,5,9,15,10]
  • 交换 10 和 15 因为 gcd (10,15) = 5 。nums = [3,5,9,10,15]

提示：

  • 1 <= nums.length <= 3 * 10^4
  • 2 <= nums[i] <= 10^5

# 分解质因数 + 并查集

每个数看作一个点，那么只有二者的 gcd>1gcd > 1 时，才会有边。

若直接每两个元素建图，那么时间复杂度为 n2n^2 级别。

我们可以用质因数作为中间点，让元素与其所有的质因数构成边。

img

最后按照连通分量对元素进行分类，对同一个连通分量的元素进行排序（因为同一连通分量可以随意交换），并按照所在索引集合依次填入即可，最后判断是否满足非递减顺序排列。

class Solution {
    public boolean gcdSort(int[] nums) {
        // 对每一个连通分量从小到大排序
        // 以所有质因数作为转折点
        int n = nums.length;
        init(200002);
        for (int j = 0; j < n; j++) {
            int num = nums[j];
            for (int i = 2; i * i <= num; i++) {
                boolean f = false;
                while (num % i == 0) {
                    f = true;
                    num /= i;
                }
                if (f) {
                    union(j, n + i);
                }
            }
            if (num > 1) {
                union(j, n + num);
            }
        }
        // int[] : [num, cnt]
        Map<Integer, TreeMap<Integer, Integer>> map = new HashMap<>();
        // 排序后的下标
        Map<Integer, TreeSet<Integer>> idxs = new HashMap<>();
        // 合并连通分量
        for (int i = 0; i < n; i++) {
            int j = find(i);
            TreeMap<Integer, Integer> m = map.computeIfAbsent(j, o -> new TreeMap<>(Comparator.comparingInt(o2 -> o2)));
            TreeSet<Integer> idx = idxs.computeIfAbsent(j, o -> new TreeSet<>(Comparator.comparingInt(o2 -> o2)));
            m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
            idx.add(i);
        }
        int[] arr = new int[n];
        for (Integer k : map.keySet()) {
            TreeMap<Integer, Integer> treeMap = map.get(k);
            TreeSet<Integer> idx = idxs.get(k);
            for (Integer v : treeMap.keySet()) {
                Integer cnt = treeMap.get(v);
                while (cnt-- > 0) {
                    arr[idx.pollFirst()] = v;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }
    int[] fa;
    public void init(int n) {
        fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }
    public void union(int i, int j) {
        int lAncestor = find(i);
        int rAncestor = find(j);
        fa[rAncestor] = lAncestor;
    }
    public int find(int x) {
        if (x == fa[x]) {
            return x;
        }
        return fa[x] = find(fa[x]);
    }
}
# 优化


合并元素与质因数，最后将新数组排序，并与原数组进行比较是否处于同一个连通分量




检查 arr[i]arr[i] 与 nums[i]nums[i] 是否处于同一连通分量


7,21,37 ,21 ,3。排序后：3,7,213,7,21


    

  • 可以知道处于处于同一连通分量
    • 



5,2,6,25,2,6,2。排序后：2,2,5,62,2,5,6


    

  • 5,25,2 不处于同一连通分量
    • 





class Solution {
    public boolean gcdSort(int[] nums) {
        // 对每一个连通分量从小到大排序
        // 以所有质因数作为转折点
        int n = nums.length;
        init(200002);
        for (int j = 0; j < n; j++) {
            int num = nums[j];
            for (int i = 2; i * i <= num; i++) {
                boolean f = false;
                while (num % i == 0) {
                    f = true;
                    num /= i;
                }
                if (f) {
                    union(nums[j], 100000 + i);
                }
            }
            if (num > 1) {
                union(nums[j], 100000 + num);
            }
        }
        int[] arr = nums.clone();
        Arrays.sort(arr);
        for (int i = 0; i < n; i++) {
            if (nums[i] == arr[i]) {
                continue;
            }
            if (find(arr[i]) != find(nums[i])) {
                return false;
            }
        }
        return true;
    }
    int[] fa;
    public void init(int n) {
        fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }
    public void union(int i, int j) {
        int lAncestor = find(i);
        int rAncestor = find(j);
        fa[rAncestor] = lAncestor;
    }
    public int find(int x) {
        if (x == fa[x]) {
            return x;
        }
        return fa[x] = find(fa[x]);
    }
}


并查集 + 数学