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

雨点打透心脏的1/2处 2022-09-11 09:20 147阅读 0赞

[力扣![icon-default.png?t=L892][icon-default.png_t_L892]/images/20220828/c00f60f92bc648e3aec57e00bfe54478.png][icon-default.png_t_L892_icon-default.png_t_L892_https_leetcode-cn.com_problems_find-greatest-common-divisor-of-array]

难度简单3

给你一个整数数组 `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`

通过次数6,585提交次数7,977

方法一：循环求解；

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_17_color_FFFFFF_t_70_g_se_x_16][]

class Solution {
        public int findGCD(int[] nums) {
            //循环测试法
    
            Arrays.sort(nums);  //先排序找出最大最小值。
            int max = nums[0];
            int min = nums[nums.length-1];
            int n = Math.min(max,min);
            for(int i = n;i>=1;i--)
            {
                if(min%i==0 && max%i==0) return i;
            }
            return 1;
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16][]

方案二：欧几里得算法;

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_17_color_FFFFFF_t_70_g_se_x_16 1][]

class Solution {
        public int findGCD(int[] nums) {
            //欧几里得算法：辗转相除法
    
            Arrays.sort(nums);
            int min = nums[0];
            int max = nums[nums.length-1];
    
            while(min != 1)
            {
                if(max%min == 0 ) return min;
                else
                {
                    int temp = max%min;
                    max = min;
                    min = temp;
                }
            }
            return min;
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

[icon-default.png_t_L892]: https://csdnimg.cn/release/blog_editor_html/release1.9.1/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=L892
[icon-default.png_t_L892_icon-default.png_t_L892_https_leetcode-cn.com_problems_find-greatest-common-divisor-of-array]: /images/20220828/c00f60f92bc648e3aec57e00bfe54478.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1c208e34fac44f1d8b4fbb103dfcf637.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/80c78d95b2d144f6a71c74c51039d015.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_17_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d0ea38b35d6c495e9602cf9d9f05bb67.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/1a7a41f43a2a4abba723f351bb548410.png