跳至主要內容

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


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

🟢   🔖  数组 数学 数论  🔗 力扣open in new window LeetCodeopen in new window

题目

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字符串的最大公因子[✓]数学 字符串🟢🀄️open in new window 🔗open in new window
1819序列中不同最大公约数的数目数组 数学 计数 1+🔴🀄️open in new window 🔗open in new window
1952三除数[✓]数学 枚举 数论🟢🀄️open in new window 🔗open in new window
2413最小偶倍数数学 数论🟢🀄️open in new window 🔗open in new window
2447最大公因数等于 K 的子数组数目数组 数学 数论🟠🀄️open in new window 🔗open in new window
3336最大公约数相等的子序列数量🔴🀄️open in new window 🔗open in new window