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

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

1. 解题思路

这道题要求我们找出数组中的最大值和最小值，并计算它们的最大公约数（GCD）。

题目本身并不复杂。最直接的做法就是先对数组进行排序，随后取出首尾两个元素：

• nums[0]：排序后的第一个元素，也就是最小值。
• nums[-1]（Python）或 nums[nums.size() - 1]（C++）：排序后的最后一个元素，也就是最大值。

得到这两个数后，再使用最大公约数函数计算即可。

这里不需要自己实现辗转相除法，因为 Python 和 C++ 都提供了现成的相关函数。

2. 代码实现

Python 代码：

import math
class Solution:
    def findGCD(self, nums: List[int]) -> int:
        nums.sort()
        return math.gcd(nums[0], nums[-1])

Python 的 math 模块提供了 gcd() 函数，可以直接计算两个整数的最大公约数。

其中，nums.sort() 会对原数组进行升序排序，而 nums[-1] 可以直接获取数组中的最后一个元素。

C++ 代码：

class Solution {
public:
    int findGCD(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return __gcd(nums[0], nums[nums.size() - 1]);
    }
};

C++ 版本的思路完全相同，先使用 sort() 对数组进行升序排序，再取出首尾两个元素。

这里使用的 __gcd() 是 GNU C++ 环境提供的扩展函数，可以计算两个整数的最大公约数。

如果使用 C++17 或更新的标准，也可以通过 <numeric> 头文件中的 std::gcd() 完成相同的计算。

3. 复杂度分析

假设数组长度为 n。

排序的时间复杂度为 O(n log n)，而求两个整数的最大公约数需要对数级时间。

因此，整个算法的时间复杂度主要由排序决定，为：

实际上，如果只需要最大值和最小值，并不一定要对整个数组排序。分别遍历数组寻找最大值和最小值，也可以完成这道题。

不过，这里采用排序的方法，代码简洁直观，对于这道题的数据规模已经足够。