
本文介绍在数组中寻找任意两个元素的最大公约数(gcd)的最优解法,重点解决暴力双重循环导致的超时问题,并给出时间复杂度更低的数学优化方案(基于因数枚举+频次统计),附完整java实现与关键注意事项。
本文介绍在数组中寻找任意两个元素的最大公约数(gcd)的最优解法,重点解决暴力双重循环导致的超时问题,并给出时间复杂度更低的数学优化方案(基于因数枚举+频次统计),附完整java实现与关键注意事项。
暴力解法(如题中所示的双重循环 + 辗转相除)的时间复杂度为 O(n² log max(aᵢ)),当数组长度 n 达到 10⁴ 量级时,运算次数将超过 10⁸,极易触发超时(TLE)。真正的高效解法应避开枚举所有数对,转而利用“公约数必为某数的因数”这一性质,采用因数频次统计法(也称“倍数筛法”或“GCD 分桶法”)。
核心思路:逆向思维——不枚举数对,而枚举可能的 GCD 值
设数组最大值为 M,则任意两数的 GCD 不会超过 M。我们可枚举 g = M 降序到 1,检查是否存在至少两个数能被 g 整除——若存在,则 g 就是答案(因从大到小枚举,首个满足条件的 g 即为最大 GCD)。
具体步骤如下:
- 预处理:用布尔数组
exists[]标记每个数值是否在原数组中出现; - 对每个候选
g(从maxVal到1),统计有多少个g的倍数存在于数组中(即exists[g], exists[2g], exists[3g], ... ≤ maxVal); - 若倍数个数 ≥ 2,则
g是某一对数的公约数,且因降序遍历,直接返回g。
该方法时间复杂度为 O(M log M)(调和级数求和),当 M ≤ 10⁶ 时非常高效,远优于 O(n²)。
✅ 优化版 Java 实现(含 Scanner 关闭与边界处理)
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
int maxVal = 0;
for (int i = 0; i = 1; g--) {
int count = 0;
// 统计 g 的倍数在数组中出现的次数
for (int multiple = g; multiple = 2) break; // 提前终止
}
}
if (count >= 2) return g;
}
return 1; // 理论上至少存在 gcd(1,1)=1,但题目保证有解
}
}
⚠️ 关键注意事项
-
Scanner必须显式关闭:sc.close()不仅避免资源泄漏,在部分 OJ 平台(如 HackerRank)中未关闭会导致运行时错误; -
数组大小限制:
exists[]长度为maxVal + 1,需确保maxVal在内存允许范围内(一般 ≤ 10⁶ 安全); -
重复元素处理:本方案天然支持重复值(如
[4, 4]→ GCD=4),因exists[4] = true后,count在第一次multiple=4时加 1,第二次仍为 1 —— 但注意:若数组含相同值两次,exists[]无法区分频次!因此需改用频次数组freq[](int[])来准确计数。更鲁棒的实现如下:int[] freq = new int[maxVal + 1]; for (int num : nums) freq[num]++; // … 在内层循环中:count += freq[multiple];
总结
暴力法适用于小规模数据(n ≤ 10³),而因数枚举法是解决大规模 Max GCD Pair 问题的标准优解。其本质是将“找数对”转化为“找公共因数”,利用数学性质降维打击。掌握此思想,不仅可用于 GCD,还可迁移至 LCM、共因子分析等场景。











