[数据结构与算法]Leetcode之1979.找出数组的最大公约数

题目

题目描述

给你一个整数数组 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 <= 1000
• 1 <= nums[i] <= 1000

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-greatest-common-divisor-of-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

解法1

class Solution {
    /**
     * <p>思路：循环判断。</p>
     * <p>结果：成功</p>
     * <ul>
     *     <li>执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户</li>
     *     <li>内存消耗：37.9 MB, 在所有 Java 提交中击败了96.92% 的用户</li>
     *     <li>通过测试用例：215 / 215</li>
     * </ul>
     *
     * @param nums 整数数组
     * @return 最大数和最小数的最大公约数
     */
    public int findGCD(int[] nums) {
        // 第一步，求得数组中的最大数和最小数
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 第二步，判断最大公约数
        // 如果最大数对最小数取余，如果等于0那么最小数一定是最大公约数
        if (max % min == 0) {
            return min;
        } else {
            // 如果不等于，那么从最小数开始遍历，寻找最大公约数
            for (int i = min; i > 0; i--) {
                // 即最大数和最小数同时对i取余，为零者则是最大公约数
                if (max % i == 0 && min % i == 0) {
                    return i;
                }
            }
        }
        return 1;
    }
}

解法2

public class Solution {
    /**
     * <p>思路：辗转相除法。两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
     * 例如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。
     * 首先，计算出a除以b的余数c，把问题转化成求b和c的最大公约数；然后计算出b除以c的余数d，
     * 把问题转化成求c和d的最大公约数；再计算出c除以d的余数e，把问题转化成求d和e的最大公约数……以此类推，
     * 逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。</p>
     *
     * <p>结果：成功</p>
     * <ul>
     *     <li>执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户</li>
     *     <li>内存消耗：37.9 MB, 在所有 Java 提交中击败了97.13% 的用户</li>
     *     <li>通过测试用例：215 / 215</li>
     * </ul>
     *
     * @param nums 整数数组
     * @return 最大数和最小数的最大公约数
     */
    public int findGCD(int[] nums) {
        // 第一步，求得数组中的最大数和最小数
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 第二步，不断辗转相除
        return gcd(max, min);
    }

    /**
     * <p>求两个数的最大公约数，利用辗转相除法。</p>
     *
     * @param a 第一个整数
     * @param b 第二个整数
     * @return 最大公约数
     */
    private int gcd(int a, int b) {
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        if (max % min == 0) {
            return min;
        }
        return gcd(max % min, min);
    }
}

解法3

public class Solution {
    /**
     * <p>思路：更相减损术：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
     * 例如10和25，25减10的差是15，那么10和25的最大公约数，等同于10和15的最大公约数。由此，我们同样可以通过递归来简化问题。
     * 首先，计算出a和b的差值c（假设a>b），把问题转化成求b和c的最大公约数；然后计算出c和b的差值d（假设c>b），
     * 把问题转化成求b和d的最大公约数；再计算出b和d的差值e（假设b>d），把问题转化成求d和e的最大公约数……</p>
     * <p>结果：成功</p>
     * <ul>
     *     <li>执行用时：1 ms, 在所有 Java 提交中击败了67.14% 的用户</li>
     *     <li>内存消耗：37.6 MB, 在所有 Java 提交中击败了99.84% 的用户</li>
     *     <li>通过测试用例：215 / 215</li>
     * </ul>
     *
     * @param nums 整数数组
     * @return 最大数和最小数的最大公约数
     */
    public int findGCD(int[] nums) {
        // 第一步，求得数组中的最大数和最小数
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 第二步，不断更相减损术
        return gcd(max, min);
    }

    /**
     * <p>求两个数的最大公约数，利用更相减损术。</p>
     *
     * @param a 第一个整数
     * @param b 第二个整数
     * @return 最大公约数
     */
    private int gcd(int a, int b) {
        if (a == b) {
            return a;
        }
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        return gcd(max - min, min);
    }
}

解法4

public class Solution {
    /**
     * <p>思路：把辗转相除法和更相减损术的优势结合起来，在更相减损术的基础上使用移位运算。思想如下：
     * <ul>
     *     <li>当a和b均为偶数时，gcd(a,b) = 2×gcd(a/2, b/2) = 2×gcd(a>>1,b>>1)。</li>
     *     <li>当a为偶数，b为奇数时，gcd(a,b) = gcd(a/2,b) = gcd(a>>1,b)。</li>
     *     <li>当a为奇数，b为偶数时，gcd(a,b) = gcd(a,b/2) = gcd(a,b>>1)。</li>
     *     <li>当a和b均为奇数时，先利用更相减损术运算一次，gcd(a,b)=gcd(b,a-b)，此时a-b必然是偶数，然后又可以继续进行移位运算。</li>
     * </ul>
     * </p>
     * <p>例如，计算10和25的最大公约数的步骤如下：</p>
     * <ul>
     *     <li>1. 整数10通过移位，可以转换成求5和25的最大公约数。</li>
     *     <li>2.利用更相减损术，计算出25-5=20，转换成求5和20的最大公约数。</li>
     *     <li>3. 整数20通过移位，可以转换成求5和10的最大公约数。</li>
     *     <li>4. 整数10通过移位，可以转换成求5和5的最大公约数。</li>
     *     <li>5. 利用更相减损术，因为两数相等，所以最大公约数是5。</li>
     * </ul>
     *
     * <p>结果：成功</p>
     * <ul>
     *     <li>执行用时：1 ms, 在所有 Java 提交中击败了67.14% 的用户</li>
     *     <li>内存消耗：38 MB, 在所有 Java 提交中击败了86.11% 的用户</li>
     *     <li>通过测试用例：215 / 215</li>
     * </ul>
     *
     * @param nums 整数数组
     * @return 最大数和最小数的最大公约数
     */
    public int findGCD(int[] nums) {
        // 第一步，求得数组中的最大数和最小数
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 第二步
        return gcd(max, min);
    }

    /**
     * <p>求两个数的最大公约数，利用更相减损术。</p>
     *
     * @param a 第一个整数
     * @param b 第二个整数
     * @return 最大公约数
     */
    private int gcd(int a, int b) {
        if (a == b) {
            return a;
        }
        /*如果a和b都是偶数
            if(a%2==0&&b%2==0){
                return gcd(a/2, b/2)*2;
            }
         */
        if ((a & 1) == 0 && (b & 1) == 0) {
            return gcd(a >> 1, b >> 1) << 1;
        }
        /*如果a是偶数，b是奇数
            else if(a%2==0&&b%2!=0){
                return gcd(a/2, b);
            }
         */
        else if ((a & 1) == 0 && (b & 1) != 0) {
            return gcd(a >> 1, b);
        }
        /*如果a是奇数，b是偶数
            else if(a%2!=0&&b%2==0){
                return gcd(a, b/2);
            }
         */
        else if ((a & 1) != 0 && (b & 1) == 0) {
            return gcd(a, b >> 1);
        }
        /*如果a和b都是奇数
            else(a%2!=0&&a%2!=0){
                int max = Math.max(a, b);
                int min = Math.min(a, b);
                return gcd(max - min, min);
            }
         */
        else {
            int max = Math.max(a, b);
            int min = Math.min(a, b);
            return gcd(max - min, min);
        }
    }
}