【LeetCode解题报告】《算法基础013_最大公约数》- Java

一、1979.找出数组的最大公约数

1.题目

1979.找出数组的最大公约数

给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。
两个数的 最大公约数 是能够被两个数整除的最大正整数。
2 <= nums.length <= 1000
1 <= nums[i] <= 1000

2.分析

这道题涉及到的知识点：

1. 被除数和除数：若 a / b = c，则 a 称作被除数，b 称作除数，c 称作商
2. 辗转相除法求最大公约数：用较大数除以较小数，之后每次都用除数除以得出来的余数，直到余数为0时，该除数就是两个数的最大公约数
   例子：求6731和2809的最大公约数
   6731 / 2809 = 2 余 1113, 2809 / 1113 = 2 余 583， 1113 / 583 = 1 余 530
   583 / 530 = 1 余 53, 530 / 53 = 10 余 0
   所以：53是6731和2809的最大公约数。

方法一：朴素法

1. 先从数组中找到最大值和最小值，再求这两个数的最大公约数。
2. 从最小值开始遍历，每次循环自减，直到找到第一个能够同时整除最大、最小值的数，就是最大公约数。

方法二：辗转相除法

1. 先从数组中找到最大值 max 和最小值 min
2. 因为不知道具体需要循环的次数，这里可以定义 while(true){} 死循环求最大公约数
3. 用最大值对最小值取模，max % min。若余数 t 不为0，则用算式的除数对余数取模，即$$max=min;min=t;$$
4. 若余数 t 为0，则返回该算式的除数，即 min

3.代码

方法一：朴素法

    public int findGCD(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int i = 1;i < nums.length;i++){
            max = nums[i] > max ? nums[i] : max;
            min = nums[i] < min ? nums[i] : min;
        }
        int t = min;
        while (t >= 1){
            if (min % t == 0 && max % t == 0){
                return t;
            }
            t--;
        }
        //这一行的返回值写多少都一样，因为一定不会走到这里
        return 0;
    }

方法二：辗转相除法

    public int findGCD2(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int i = 1;i < nums.length;i++){
            max = nums[i] > max ? nums[i] : max;
            min = nums[i] < min ? nums[i] : min;
        }
        while (true){
            int t = max % min;
            //如果较大数除以较小数余数不为0，则除数变为被除数，余数变为除数
            if (t != 0){
                max = min;
                min = t;
            } else {
                //如果余数为0，则当前算式的除数就是最大公约数
                return min;
            }
        }
    }

二、1819. 序列中不同最大公约数的数目

1.题目

1819. 序列中不同最大公约数的数目

给你一个由正整数组成的数组 nums 。
数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
  · 例如，序列 [4,6,16] 的最大公约数是 2 。
数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。
  · 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。
1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁵

2.分析

1. 求多个数的最大公约数：gcd ( a , b , c ) = gcd ( gcd ( a , b ) , c )
2. 根据题意，在一个数组中，若数组的最大值为 max，则必定存在任意非空序列的最大公约数 gcd ∈ [ 1, max ]。
3. 通过 i 的 倍数得到的序列的最大公约数不一定是 i，还有可能是 i 的倍数。（如：2的倍数得到的序列 [4,8,24]，最大公约数不为2，而是2的倍数 4）

思路：

1. 定义一个布尔类型数组 arr，用于标记给定数组 nums 的元素，数组初始值为false，因为 1 <= nums[i] <= 2 * 10⁵，所以数组长度为 20001。
2. 循环遍历给定数组 nums，通过标记法标记出现在nums中的元素（若给定数组存在元素 a，则标记 arr[ a ] = true;），同时，找出 nums 数组中的最大值 max。
3. 初始化最大公约数变量 gcd，循环遍历 i ∈ [ 1,max ]（这里的意义是：假设遍历到的 i 是某一个非空序列的最大公约数）
4. 再内层循环遍历 j ∈ [ i ,max ]（j = i,2i,3i,…），若布尔数组中存在 arr[ j ] = true，说明 j 在 nums中存在，则通过辗转相除法求 当前最大公约数 gcd 与 j 的最大公约数。
5. 内层循环遍历完后，得到的最大公约数就是数组中指定序列的最大公约数。
6. 根据上面分析的第3点：若gcd = i，则计数加1，否则直接进入下一循环。
7. 最后返回计数值 count。

3.代码

    public int countDifferentSubsequenceGCDs(int[] nums) {
        //定义子数组，初始值为false
        boolean[] arr = new boolean[200001];
        int max = nums[0];
        //找出数组的最大值
        for (int num : nums) {
            arr[num] = true;
            max = findMax(max, num);
        }
        //计数变量
        int i,j,count = 0;
        //最大公约数的范围为 [1,max]
        for (i = 1;i <= max;i++){
            //初始化最大公约数
            int gcd = 0;
            //假设公约数为i，能被i整除的有i，2i，3i...
            for (j = i;j <= max;j += i){
                if (arr[j]){
                    if (gcd == 0){
                        gcd = j;
                    } else {
                        gcd = findGcd2(gcd, j);
                    }

                }
            }
            if (i == gcd){
                count++;
            }
        }
        return count;
    }

    /**
     * 辗转相除法求最大公约数
     */
    private int findGcd2(int x, int y) {
        if (x == 0) {
            return y;
        }
        return findGcd2(y % x, x);
    }

    /**
     * 求两个数最大值
     */
    int findMax(int a,int b){
        return a > b ? a : b;
    }