[NC]151. 最大公约数

🚩传送门：牛客题目

题目

给定两个数，求解a和b的最大公约数。两个数的 最大公约数 是能够被两个数整除的最大正整数。

示例 1：

输入：3，6 输出：3

示例 1：

输入：8，12 输出：4

🚩解题思路1：辗转相除法（欧几里德法）

算法流程：

1. 小数放min中，大数放max中 。
2. 求max/min的余数，若余数为0，则min是余数，若不是0，max=min，min=余数
3. 重复递归，直至余数为0。

复杂度分析

时间复杂度：，其中 是二者中最大值。

空间复杂度：，使用的额外空间复杂度为常数。

官方代码

class Solution {
    int gcd(int min,int max){  // max:被除数 min:除数, 确保 min<max
        if(max==0) return min;
        return gcd(min,max%min);
    }
}

解题思路2：辗转相减法（尼考曼彻斯法）

算法流程：

1. 小数放min中，大数放max中 。

2. 求max-min

   若结果为0，则min or max是答案，若结果不是0，则max=min，min=结果。

3. 重复递归，直至结果为0。

复杂度分析

时间复杂度：，其中 是二者中最大值。

空间复杂度：，使用的额外空间复杂度为常数。

官方代码

class Solution {
    int gcd(int min,int max){  // max:被减数 min:减数, 确保 min<max
        if(max<min)return gcd(max,min);
        if(max-min==0)  return max;
        return gcd(min,max-min);
    }
}