题解 | #最大公约数#

思路：

题目的主要信息：

• 找到两个数a与b的最大公约数
• a与b最小为1，无特殊情况

最常规的求公因数，以下罗列几种方法。
方法一：穷举法
具体做法：
优先考虑a与b一个是另一个因子的情况，可以直接返回。
然后找到较小值，由小到大穷举2到较小值的所有数字，遇到公约数更新答案。

class Solution {
public:
    int gcd(int a, int b) {
        if(a % b == 0) //当一个数是另一个数因数时
            return b;
        if(b % a == 0)
            return a;
        int n = a > b ? b : a;  //等于较小值
        int res = 1;
        for(int i = 2; i < n; i++){ //穷举到较小值 
            if(a % i == 0 && b % i == 0) //公因数
                res = i;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，a与b即为两个数的大小
• 空间复杂度：，无额外空间使用

方法二：辗转相除法
具体做法：
依赖于欧几里得算法，相互大数除小数取余，然后小数再除余，到0为止。

class Solution {
public:
    int gcd(int a, int b) {
        if(a % b == 0) //当一个数是另一个数因数时
            return b;
        if(b % a == 0)
            return a;
        int temp;
        //比较两个数的大小，值大的数为a，值小的数为b
        if (a < b) {
            temp = a;
            a = b;
            b = temp;
        }
        //求余
        while (b != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
};

复杂度分析：

• 时间复杂度：，欧几里得算法是指数增长的
• 空间复杂度：，无额外空间使用

方法三：更相减损法
有一个性质：两个数的最大公约数等于它们中较小的数和两数之差的最大公约数。

具体做法：
模拟上述过程即可。

class Solution {
public:
    int gcd(int a, int b) {
        int temp = abs(a - b); //取差的绝对值  
        while(temp != 0) //不断减去差的绝对值直到为0
        {
            a = b;
            b = temp;
            temp = abs(a - b);
        }
        return b;
    }
};

复杂度分析：

• 时间复杂度：最坏情况为，最坏一个一个减，全部减完
• 空间复杂度：，无额外空间