1979. 找出数组的最大公约数
1979. 找出数组的最大公约数
题目
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)**来高效计算。
找到数组中的最大值和最小值:
- 直接使用 Math.max 和 Math.min 找到最大值和最小值。
计算最大公约数:
- 使用辗转相除法:
- 如果
b = 0
,则GCD(a, b) = a
。 - 否则,递归计算
GCD(b, a \mod b)
。
- 如果
- 使用辗转相除法:
返回计算结果。
复杂度分析
时间复杂度:
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 | 最大公约数相等的子序列数量 | 🔴 | 🀄️ 🔗 |