个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法
推荐一款面试、刷题神器牛客网：👉点击开始刷题学习👈
1. 题目
描述
如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。
输入 a 和 b , 请返回 a 和 b 的最大公约数。
数据范围：
1
≤
a
,
b
≤
1
0
9
1 \le a,b \le 10^9
1≤a,b≤109
进阶： 空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)
2. 算法设计思路
思路一：简单暴力法
我们只需要先比较a和b，将较小的那个值记为min。然后从min开始，逐个整数递减尝试，如果尝试到 i 时可以同时整除a和b，则停止尝试，并返回 i 值。
为什么要从 min 开始递减，而不是从 1 开始递增呢？想一想：我们要求的是最大公约数。
思路二：辗转相除法
gcd()为求最大公约数的函数
反复使用：
g
c
d
(
a
,
b
)
<
=
>
g
c
d
(
b
,
a
%
b
)
gcd(a,b)<=>gcd(b,a\%b)
gcd(a,b)<=>gcd(b,a%b)
这里我们不做数学上的证明，有兴趣可以自行网络搜索证明过程。
3. 代码实现
注：这里并不是完整代码，而只是核心代码的模式
思路一代码：
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 求出a、b的最大公约数。
* @param a int
* @param b int
* @return int
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int gcd(int a, int b ) {
int min = a > b ? b : a;
for(int i = min; i > 0; i--){
if(a % i == 0 && b % i == 0){
return i;
}
}
return -1;
}
思路二代码：
int gcd(int a, int b ) {
if(b == 0){
return a;
}
return gcd(b, a%b);
}
.
4. 运行结果
成功通过啦！而且可以看到，即使我思路二采用的是递归的写法，运行的效率仍然要高很多。
结束语：
今天的分享就到这里啦，快来加入刷题大军叭！
👉点击开始刷题学习👈
CSDN话题挑战赛第2期
参赛话题：学习笔记
感谢阅读
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/114817.html
