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

🟢   🔖  数组 数学 数论  🔗 力扣 LeetCode

题目

Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums.

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Example 1:

Input: nums = [2,5,6,9,10]

Output: 2

Explanation:

The smallest number in nums is 2.

The largest number in nums is 10.

The greatest common divisor of 2 and 10 is 2.

Example 2:

Input: nums = [7,5,6,8,3]

Output: 1

Explanation:

The smallest number in nums is 3.

The largest number in nums is 8.

The greatest common divisor of 3 and 8 is 1.

Example 3:

Input: nums = [3,3]

Output: 3

Explanation:

The smallest number in nums is 3.

The largest number in nums is 3.

The greatest common divisor of 3 and 3 is 3.

Constraints:

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

题目大意

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

最大公约数是两个整数的最大整除数，通常通过**辗转相除法（Euclidean Algorithm）**来高效计算。

1. 找到数组中的最大值和最小值：

   • 直接使用 Math.max 和 Math.min 找到最大值和最小值。

2. 计算最大公约数：

   • 使用辗转相除法：
     • 如果 b = 0，则 GCD(a, b) = a。
     • 否则，递归计算 GCD(b, a \mod b)。

3. 返回计算结果。

复杂度分析

• 时间复杂度：O(n + log(min(min, max)))

  • 找最大值和最小值：O(n)，其中 n 是数组长度。
  • 辗转相除法：由于每次递归都会减少一个因子，其时间复杂度为 O(log(min(min, max)))。
  • 总复杂度：O(n + log(min(min, max)))。

• 空间复杂度：O(1)，使用了常数级别的空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findGCD = function (nums) {
	const max = Math.max(...nums);
	const min = Math.min(...nums);
	const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
	return gcd(max, min);
};

相关题目

题号	标题	题解	标签	难度	力扣
1071	字符串的最大公因子	[✓]	数学 字符串	🟢	🀄️ 🔗
1819	序列中不同最大公约数的数目		数组 数学 计数 1+	🔴	🀄️ 🔗
1952	三除数	[✓]	数学 枚举 数论	🟢	🀄️ 🔗
2413	最小偶倍数		数学 数论	🟢	🀄️ 🔗
2447	最大公因数等于 K 的子数组数目		数组 数学 数论	🟠	🀄️ 🔗
3336	最大公约数相等的子序列数量			🔴	🀄️ 🔗