【LetMeFly】1979.找出数组的最大公约数模拟附手动gcd力扣题目链接https://leetcode.cn/problems/find-greatest-common-divisor-of-array/给你一个整数数组nums返回数组中最大数和最小数的最大公约数。两个数的最大公约数是能够被两个数整除的最大正整数。示例 1输入nums [2,5,6,9,10]输出2解释nums 中最小的数是 2 nums 中最大的数是 10 2 和 10 的最大公约数是 2示例 2输入nums [7,5,6,8,3]输出1解释nums 中最小的数是 3 nums 中最大的数是 8 3 和 8 的最大公约数是 1示例 3输入nums [3,3]输出3解释nums 中最小的数是 3 nums 中最大的数是 3 3 和 3 的最大公约数是 3提示2 nums.length 10001 nums[i] 1000解题方法遍历 库函数/手动gcd遍历一遍原始数组求出最小值和最大值使用库函数或手写函数计算最大值和最小值的最大公约数。怎么手动计算两个数的最大公约数gcd使用欧几里得算法辗转相除法可以在log ⁡ n u m s [ i ] \log nums[i]lognums[i]的时间复杂度内求出。所谓辗转相除法即两个数的最大公约数等于较小的数和两数相除余数的最大公约数即g c d ( a , b ) g c d ( b , a m o d b ) gcd(a,b)gcd(b,a\mod b)gcd(a,b)gcd(b,amodb)。递归写法比较清晰易懂但是会有一个log ⁡ \loglog级别的递归栈intgcd(inta,intb){// 要保证abreturnb?gcd(b,a%b):a;}而遍历写法不那么清晰但空间复杂度为O ( 1 ) O(1)O(1)intgcd(inta,intb){if(ab){swap(a,b);}while(b){// (a, b) (b, a % b);inttmpb;ba%b;atmp;}returna;}时间复杂度O ( l e n ( n u m s ) × log ⁡ n u m s [ i ] ) O(len(nums)\times\log nums[i])O(len(nums)×lognums[i])空间复杂度O ( log ⁡ n u m s [ i ] ) O(\log nums[i])O(lognums[i])或O ( 1 ) O(1)O(1)AC代码C/* * LastEditTime: 2026-07-18 07:01:47 */classSolution{public:intfindGCD(vectorintnums){intmnums[0],Mm;for(intt:nums){mmin(m,t);Mmax(M,t);}returngcd(m,M);}};C —— 迭代gcd/* * LastEditTime: 2026-07-18 07:23:34 */classSolution{private:intgcd1979(inta,intb){if(ab){swap(a,b);}while(b){// (a, b) (b, a % b);inttmpb;ba%b;atmp;}returna;}public:intfindGCD(vectorintnums){intmnums[0],Mm;for(intt:nums){mmin(m,t);Mmax(M,t);}returngcd1979(m,M);}};Python LastEditTime: 2026-07-18 07:04:07 fromtypingimportListfrommathimportgcdclassSolution:deffindGCD(self,nums:List[int])-int:returngcd(min(nums),max(nums))Java/* * LastEditTime: 2026-07-18 07:06:24 */classSolution{publicintfindGCD(int[]nums){intmnums[0],Mm;for(intt:nums){mMath.min(m,t);MMath.max(M,t);}returngcd(M,m);}privateintgcd(inta,intb){if(b0){returna;}returngcd(b,a%b);}}Go/* * LastEditTime: 2026-07-18 07:10:26 */packagemainfuncgcd1979(a,bint)int{ifb0{returna}returngcd1979(b,a%b)}funcfindGCD(nums[]int)int{m:nums[0]M:mfor_,t:rangenums{mmin(m,t)Mmax(M,t)}returngcd1979(M,m)}Rust/* * LastEditTime: 2026-07-18 07:15:10 */implSolution{pubfnfind_gcd(nums:Veci32)-i32{letmutm:i32nums[0];letmutM:i32m;fortinnums.iter(){// 记得t解引用mm.min(t);MM.max(t);}Self::gcd(M,m)}fngcd(a:i32,b:i32)-i32{ifb0{a}else{Self::gcd(b,a%b)}}}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源