目录
- 题目描述:
- 输入:
- 输出:
- 代码实现:
题目描述:
给你一个整数数组 nums ,返回数组中最大数和最小数的 最大公约数 。
两个数的 最大公约数 是能够被两个数整除的最大正整数。
输入:
nums = [2,5,6,9,10]
输出:
2
解释:
nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2
代码实现:
class Solution {
public int findGCD(int[] nums) {
/*
* 排序,再调用最大公约数函数
* Arrays.sort(nums);
* return gcd(nums[nums.length - 1], nums[0]);
*/
//不排序,打擂台的形式
int max = nums[0];// 求最大值
int min = nums[0];// 最最小值
for (int i = 0; i < nums.length; i++) {// 遍历一次,得到最大最小
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
return gcd(max, min);// 调用最大公约数函数
}
public int gcd(int a, int b) {
/*第一种方法:递归
* if (a == 0) {//递归出口
* return b;
* }
* if (b == 0) {//递归出口
* return a;
* }
* return gcd(b, a % b);//辗转相除法:gcd(a,b) = gcd(b,a%b)
*/
//第二种方法:正常辗转相除
int remainder = -1;// 余数
while (remainder != 0) {// 余数为0跳出循环
remainder = a % b;// 计算余数
a = b;// 被除数变余数
b = remainder;// 余数变除数
}
return a;// 返回最后一轮的被除数
}
}