如何高效快速地从数组中查找与所有其他元素互质的元素？

嘿，这个问题我之前也碰到过，咱们先拆解下原代码里的问题，再一步步优化，让效率提上来~

首先说原代码里的几个明显问题：

1. GCD算法效率低：你用的是减法实现的GCD，对于大数来说会慢很多，比如计算gcd(1000000, 1)要循环999999次，换成取模版的欧几里得算法瞬间就能出结果。
2. 重复计算太多：数组里如果有重复元素，你还是会一次次重复计算它们和当前元素的GCD，完全没必要。
3. 逻辑bug：你判断elementsCount[i] == inputs.length，但你只在i≠j的时候计数，所以最多只能到inputs.length - 1，这个条件永远不会触发，等于白写了...
4. 没有提前终止：只要发现当前元素和某个其他元素不互质，其实可以直接跳过这个元素的后续检查，不用继续循环。

接下来咱们一步步优化：

第一步：替换成高效的GCD实现 #

把原来的减法GCD换成取模版的欧几里得算法，时间复杂度直接从O(n)降到O(log(min(a,b)))，代码如下：

static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
// 或者迭代版，避免递归栈溢出（不过int范围内递归没问题）
static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

第二步：减少重复计算，预处理唯一元素 #

先统计数组中每个元素的出现次数，再提取唯一元素集合。这样我们只需要对每个唯一元素做一次检查，而不是遍历原数组的每个元素，尤其是数组有大量重复元素时，能省超多计算。

第三步：优化判断逻辑，提前终止 #

对于每个唯一元素x：

• 如果x出现多次：只有当x是1的时候才可能符合条件（因为gcd(1,1)=1），其他重复元素直接排除（比如两个2的gcd是2≠1，肯定不符合）。
• 如果x只出现一次：检查它和所有其他唯一元素的gcd是否都是1，一旦发现某个元素和x不互质，立刻终止检查，不用继续。

优化后的完整代码 #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class CoprimeFinder {

    public static ArrayList<Integer> getAllCoPrimes(int[] inputs) {
        ArrayList<Integer> coprimes = new ArrayList<>();
        if (inputs.length == 0) return coprimes;

        // 统计每个元素的出现次数
        Map<Integer, Integer> elementCount = new HashMap<>();
        for (int num : inputs) {
            elementCount.put(num, elementCount.getOrDefault(num, 0) + 1);
        }

        // 获取所有唯一元素
        Set<Integer> uniqueElements = elementCount.keySet();

        // 遍历每个唯一元素，判断是否符合条件
        for (int x : uniqueElements) {
            boolean isValid = true;

            // 处理重复元素的情况
            if (elementCount.get(x) > 1) {
                if (x != 1) {
                    isValid = false;
                }
                // 1和自己的gcd是1，继续检查其他元素
            }

            // 如果还没被排除，检查和其他所有唯一元素的gcd是否为1
            if (isValid) {
                for (int y : uniqueElements) {
                    if (x != y && gcd(x, y) != 1) {
                        isValid = false;
                        break; // 提前终止，节省时间
                    }
                }
            }

            // 如果符合条件，把原数组中所有的x都加入结果
            if (isValid) {
                int count = elementCount.get(x);
                for (int i = 0; i < count; i++) {
                    coprimes.add(x);
                }
            }
        }

        return coprimes;
    }

    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

优化后的时间复杂度分析 #

假设原数组长度为n，唯一元素的数量为k（k ≤ n）：

• 预处理统计次数：O(n)
• 遍历唯一元素：O(k)
• 每个唯一元素检查其他k-1个元素：O(k)
  所以总时间复杂度是O(n + k²)，而原代码是O(n²)。当数组有大量重复元素时，k远小于n，效率提升非常明显。比如数组有1000个元素，其中只有10个唯一元素，原代码要算1e6次GCD，优化后只需要算100次，差距巨大。

最后再提个小优化：如果唯一元素集合里有一个大于1的公约数d，那所有能被d整除的元素都不可能符合条件，可以提前过滤掉，但这个对于普通场景来说收益不大，除非数组的元素有明显的公共因数。

内容的提问来源于stack exchange，提问作者Amos George