2025年力扣5866. 数组的最大公因数排序

科技前沿 • 2025-01-04 16:30 • 阅读 71

大家好，我是讯享网，很高兴认识大家。

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

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

#define N  int fathers[N]; // 求最大公因数 // 以后手写了，有个好东西！ //__gcd(x, y) class Solution { 
    public: int find(int cur) { 
    if (fathers[cur] == cur) return cur; return (fathers[cur] = find(fathers[cur])); } void merge(int a, int b) { 
    int fa = find(a); int fb = find(b); fathers[fa] = fb; } bool gcdSort(vector<int> &nums) { 
    for (int i = 0; i < N; i++) fathers[i] = i; //最少量地存储，比如24存：2； 22存：2、11  for(int num: nums){ 
    int temp = num; for(int i=2; i*i<=temp; i++){ 
    if(temp%i!=0) continue; while(temp%i==0) temp /= i; merge(num, i); } if(temp>1) merge(num, temp); } // 最原始的求所有因素的做法，比较慢，不过还是能过 for(int num: nums){ 
    for(int i=2; i<=sqrt(num); i++){ 
    if(num%i==0) { 
    merge(num, i); merge(num, num/i); } } } vector<int> copy = nums; sort(copy.begin(), copy.end(), less<int>()); for(int i=0; i<nums.size(); i++){ 
    if(copy[i]==nums[i]) continue; // printf("%d %d %d %d\n", copy[i], nums[i], find(copy[i]), find(nums[i])); if(find(copy[i])!=find(nums[i])) return false; } return true; } };

讯享网

2025年力扣5866. 数组的最大公因数排序

相关推荐