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 * 104
2 <= nums[i] <= 105

解题思路

1.题意为任意两个数的公因数大于1，那么这两个数可以交换。由此可知如果a和b可交换，b和c可交换，那么a,b,c三者可以任意改变顺序，不难想到用并查集把所有公因数大于1的两个数合并。

2.如果用两层循环来判断来合并任意两个数，此时必然会超时。因此考虑将每个数和自己的所有质因子进行合并，如15和质因子3，5进行合并，21和质因子3，7合并，这样保证了21和15在同一个集合中。这样对于每个数仅仅需要分解质因子的时间复杂度，远远低于两层循环所需的时间复杂度。

3.合并之后，所有在一个并查集中的数可以任意交换。将原有的数组进行排序和新数组对比，如果原有数组和新数组的数字相同，则跳过，如果不同，则必须满足两个数在同一个并查集中，否则返回false，扫描一遍后如果没有返回false，则返回true.

代码

const int N = 3e5 + 10;

class Solution {
private:
    int p[N];
public:
    int find(int x) {
        if (x != p[x])  p[x] = find(p[x]);
        return p[x];
    }
    void merge(int a, int b) {
        int x = find(a), y = find(b);
        if (x == y)     return;
        p[x] = y;
    }
    bool gcdSort(vector<int>& nums) {
        vector<int> nums1 = nums;
        for (int i = 1; i < N; i++) p[i] = i;
        // 分解质因数
        for (auto c:nums) {
            int k = c;
            for (int i = 2; i <= c / i; i++) {
                bool flag = false;
                while (c % i == 0)
                    c /= i, flag = true;
                if (flag)
                    merge(k, i);
            }
            // 合并质因子
            if (c > 1)
               merge(k, c);
        }
        sort(nums1.begin(), nums1.end());
        // 对比原数组
        for (int i = 0; i < nums1.size(); i++) {
            if (nums1[i] == nums[i])    continue;
            if (find(nums1[i]) != find(nums[i]))    return false;
        }
        return true;
    }
};