LeetCode 解題筆記：1979. Find Greatest Common Divisor of Array

作者：王一哲
日期：2026年7月18日


LeetCode 題目連結：1979. Find Greatest Common Divisor of Array

解題想法

簡單題。題目給一個陣列 $nums$，回傳陣列中最小值與最大值的最大公因數。因為 Python 與 C++ 都有找最小值、最大值、最大公因數的工具，可以一行解。如果不使用這些工具，也可以用一個 for 迴圈掃過 $nums$ 找最小值與最大值，另外再寫一個自訂函式用輾轉相除法求最大公因數。因為測資很小，兩種寫法都很快。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.26 MB, beats 80.59%.

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        return gcd(min(nums), max(nums))

Runtime: 0 ms, beats 100.00%. Memory: 19.27 MB, beats 80.59%.

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        imin, imax = float('inf'), float('-inf')
        for num in nums:
            if num < imin:
                imin = num
            if num > imax:
                imax = num
        
        def mygcd(a, b):
            while b:
                a, b = b, a%b
            return a
        
        return mygcd(imin, imax)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 16.10 MB, beats 92.83%.

class Solution {
public:
    int findGCD(vector<int>& nums) {
        return gcd(*min_element(nums.begin(), nums.end()), *max_element(nums.begin(), nums.end()));
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 16.20 MB, beats 68.79%.

class Solution {
public:
    int mygcd(int a, int b) {
        while(b) {
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
    
    int findGCD(vector<int>& nums) {
        int imin = 1000000000, imax = -1000000000;
        for(int num : nums) {
            if (num < imin) imin = num;
            if (num > imax) imax = num;
        }
        return mygcd(imin, imax);
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.12 MB, beats 62.69%.

int mygcd(int a, int b) {
    while(b) {
        int r = a%b;
        a = b;
        b = r;
    }
    return a;
}

int findGCD(int* nums, int numsSize) {
    int imin = 1000000000, imax = -1000000000;
    for(int i = 0; i < numsSize; i++) {
        int num = nums[i];
        if (num < imin) imin = num;
        if (num > imax) imax = num;
    }
    return mygcd(imin, imax);
}