文章目錄
-
- 1. 題目
- 2. 解題
1. 題目
給你一個整數數組 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
複制
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/find-greatest-common-divisor-of-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
2. 解題
class Solution:
def findGCD(self, nums: List[int]) -> int:
nums.sort()
return math.gcd(nums[0], nums[-1])
複制
36 ms 15.1 MB Python3
class Solution {
public:
int findGCD(vector<int>& nums) {
sort(nums.begin(), nums.end());
return __gcd(nums[0], nums.back());
}
};
複制
4 ms 12.1 MB C++
class Solution { // 自己實作gcd
public:
int findGCD(vector<int>& nums) {
sort(nums.begin(), nums.end());
return mygcd(nums[0], nums.back());
}
int mygcd(int x, int y)
{
int r;
while(y)
{
r = x%y;
x = y;
y = r;
}
return x;
}
};
複制
我的CSDN部落格位址 https://michael.blog.csdn.net/
長按或掃碼關注我的公衆号(Michael阿明),一起加油、一起學習進步!