5866. 数组的最大公因数排序 力扣周赛（困难） 并查集，公因数

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

给你一个整数数组 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]

题解：https://leetcode-cn.com/problems/gcd-sort-of-an-array/solution/bing-cha-ji-fen-jie-zhi-yin-shu-by-xin-x-ylsz/

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

2、求每个数的因数，再合并，时间复杂度大于两个循环（本文方法）

class Solution {
public:
    int team[100005];
    int findfa(int k)
    {
        if(k!=team[k])  return team[k]=findfa(team[k]);
        return team[k];
    }
    void merge(int x,int y)
    {
        int fx=findfa(x);
        int fy=findfa(y);
        if (fx!=fy) team[fx]=fy;
        return;
    }
    bool gcdSort(vector<int>& nums) {
    int maxnum=0;
    for(auto num:nums) maxnum=max(maxnum,num);
    for(int i=1;i<=maxnum;i++) team[i]=i;
    for(auto num:nums)
    {
       /* for(int i=2;i<num;i++)
            if (num%i==0) merge(num,i);*/  // 超时写法
        int t=num;
        for(int i=2;i*i<=num;i++)
        {
            bool flag=0;
            while(t%i==0){ t/=i; flag=1;}
            if(flag) merge(num,i);
        }
        if(t>1) merge(num,t);
    }
    vector<int> a=nums;
    sort(a.begin(),a.end());
    for(int i=0;i<nums.size();i++)
    {
        if(a[i]==nums[i]) continue;
        if(findfa(a[i])!=findfa(nums[i])) return false;
    }
    return true;
    }
};