题解 | #最大公约数#

题意整理

• 输入整数a和b。
• 求a和b的最大公约数。

方法一（暴力法）

1.解题思路

由于是a和b的最大公约数，那么它的范围一定在1到 之间，我们逆序遍历这个区间，找到能同时被a和b整除的数即可。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
        // 首先求出a和b中的较小者
        int min=Math.min(a,b);

        //最大公约数一定在1到较小者之间
        for(int i=min;i>=1;i--){
            //如果同时被a，b整除，直接返回
            if(a%i==0&&b%i==0){
                return i;
            }
        }

        return 1;
    }

}

3.复杂度分析

• 时间复杂度：假设a和b的较小者为n，最坏情况下需要遍历n次，所以时间复杂度是 。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为 。

方法二（递归）

1.解题思路

• 递归终止条件：余数mod为0，此时b为最大公约数。
• 每一层递归传递什么：将a替换为b，b替换为余数mod。
• 每一层递归返回什么：当前层的余数。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
        int mod=a%b;
        //递归终止条件
        if(mod==0){
            return b;
        } 
        //只要递归没终止，将a换为b，b换为余数
        return gcd(b,mod);
    }

}

3.复杂度分析

• 时间复杂度：假设最终得到的最大公约数为d，a和b的较小者为n，我们把每次得到的余数按照逆序进行排列，那么它必然是 的形式，其中 ，由于 可以知道这个数列的增长速度比斐波那契数列快，而斐波那契数列是呈指数增长的，所以时间复杂度是 。
• 空间复杂度：需要额外深度为 的递归栈，所以空间复杂度为 。

方法三（迭代）

1.解题思路

迭代的思路和递归相同，只是用变量来记录每一次替换的值。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
        //只要b不为0，就一直替换
        while(b!=0){
            //a替换为b，b替换为余数
            int mod=a%b;
            a=b;
            b=mod;
        }
        //a记录的是变为0之前的那个余数
        return a;
    }

}

3.复杂度分析

• 时间复杂度：遍历次数和方法二递归的次数一致，所以时间复杂度是 。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为 。