⭐ 题目日期：

字节 - 2024/10/14

🌳 题目描述：

给 n 个数字，求他们的最大公约数

🕵🏽 面试评估：

这道题难度中等，考察候选人对数学算法的掌握程度。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

要求 n 个数的最大公约数，我们要知道如何计算两个数的最大公约数。常用的方法有辗转相除法。辗转相除法基于这样一个定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，要求整数 a 和 b（假设 a > b）的最大公约数，就用 a 除以 b 得到余数 r，然后把原来的除数 b 作为新的被除数，余数 r 作为新的除数，继续相除得到新的余数，如此反复，直到余数为 0 时，此时的除数就是 a 和 b 的最大公约数。

以求 18 和 12 的最大公约数为例：

• 用较大数除以较小数：18 ÷ 12 = 1……6，这里商是 1，余数是 6。
• 用上一步的除数作为新的被除数，余数作为新的除数继续相除：12 ÷ 6 = 2……0，此时余数为 0。
• 当余数为 0 时，最后一步的除数 6 就是 18 和 12 的最大公约数。

对于 n 个数字，逐一计算两两数字, 例如 n = 4, gcd(a, b, c, d) = gcd(gcd(gcd(a,b),c),d)

💻代码：

Java

public int findGCD(int[] nums) {
    int result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        result = gcd(result, nums[i]);
        if (result == 1) {
            return 1;
        }
    }

    return result;
}

private int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

Python

from typing import List

def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

def find_gcd(nums: List[int]) -> int:
    result = nums[0]
    for num in nums[1:]:
        result = gcd(result, num)
        if result == 1: 
            return 1
    return result

C++

class Solution {
public:
    int findGCD(vector<int>& nums) {
        int result = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            result = gcd(result, nums[i]);
            if (result == 1) {
                return 1; 
            }
        }
        return result;
    }

private:
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};

🚵🏻复杂度分析：

时间复杂度：O(nlogM), n 为数组的长度，M 为数组中最大的值

空间复杂度：O(1)

🔬在线评测(Online Judge):

题目链接