Easy

题目描述

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

解题思路

解题思路

这道题要求找到数组中最小值和最大值的最大公约数（GCD）。

首先分析问题：我们需要找到数组中的最小值和最大值，然后计算它们的最大公约数。

方法1：暴力枚举（题目提示的方法）

  1. 遍历数组找到最小值和最大值
  2. 从1到最小值遍历所有可能的因子，找到能同时整除两个数的最大值

方法2：欧几里得算法（推荐）

  1. 遍历数组找到最小值和最大值
  2. 使用欧几里得算法（辗转相除法）计算两数的最大公约数

欧几里得算法的核心思想是：gcd(a, b) = gcd(b, a % b)，当其中一个数为0时，另一个数就是最大公约数。

第二种方法效率更高，时间复杂度为 O(n + log(min(a,b)))，其中n是数组长度，log部分是计算GCD的时间。

由于数据规模不大（最多1000个元素，每个元素最大1000），两种方法都可以通过，但推荐使用欧几里得算法，因为它是计算GCD的标准高效算法。

代码实现

class Solution {
public:
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    int findGCD(vector<int>& nums) {
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        return gcd(minVal, maxVal);
    }
};

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        min_val = min(nums)
        max_val = max(nums)
        return gcd(min_val, max_val)

public class Solution {
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public int FindGCD(int[] nums) {
        int minVal = nums.Min();
        int maxVal = nums.Max();
        return Gcd(minVal, maxVal);
    }
}

var findGCD = function(nums) {
    const gcd = (a, b) => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    
    const minVal = Math.min(...nums);
    const maxVal = Math.max(...nums);
    return gcd(minVal, maxVal);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + log(min(min_val, max_val)))找最值需要O(n)，计算GCD需要O(log(min(a,b)))
空间复杂度O(1)只使用常数额外空间

相关题目