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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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⁴
2 <= nums[i] <= 10⁵

# 思路

并查集+分组排序

# 解法

class Solution {
    static int[] parent = new int[100005];

    public boolean gcdSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i <= 100000; i++) parent[i] = i;
        for (int num : nums) {
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    union(num, i);
                    union(num, num / i);
                }
            }
        }
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for (int x : nums) map.computeIfAbsent(find(x), k -> new PriorityQueue<>()).add(x);
        for (int i = 0; i < n; i++) nums[i] = map.get(find(nums[i])).poll();
        for (int i = 0; i < n - 1; i++) if (nums[i] > nums[i + 1]) return false;
        return true;
    }

    public void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot != yRoot) parent[yRoot] = xRoot;
    }

    public int find(int x) {
        if (parent[x] != x) return parent[x] = find(parent[x]);
        return parent[x];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 总结

分析出几种情况，然后分别对各个情况实现

#Java