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;
    }
};