题目
题目描述
给你一个整数数组 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
题解
解法1
class Solution {
/**
* <p>思路：循环判断。</p>
* <p>结果：成功</p>
* <ul>
* <li>执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户</li>
* <li>内存消耗：37.9 MB, 在所有 Java 提交中击败了96.92% 的用户</li>
* <li>通过测试用例：215 / 215</li>
* </ul>
*
* @param nums 整数数组
* @return 最大数和最小数的最大公约数
*/
public int findGCD(int[] nums) {
// 第一步，求得数组中的最大数和最小数
int max = nums[0];
int min = nums[0];
for (int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 第二步，判断最大公约数
// 如果最大数对最小数取余，如果等于0那么最小数一定是最大公约数
if (max % min == 0) {
return min;
} else {
// 如果不等于，那么从最小数开始遍历，寻找最大公约数
for (int i = min; i > 0; i--) {
// 即最大数和最小数同时对i取余，为零者则是最大公约数
if (max % i == 0 && min % i == 0) {
return i;
}
}
}
return 1;
}
}
解法2
public class Solution {
/**
* <p>思路：辗转相除法。两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
* 例如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。
* 首先，计算出a除以b的余数c，把问题转化成求b和c的最大公约数；然后计算出b除以c的余数d，
* 把问题转化成求c和d的最大公约数；再计算出c除以d的余数e，把问题转化成求d和e的最大公约数……以此类推，
* 逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。</p>
*
* <p>结果：成功</p>
* <ul>
* <li>执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户</li>
* <li>内存消耗：37.9 MB, 在所有 Java 提交中击败了97.13% 的用户</li>
* <li>通过测试用例：215 / 215</li>
* </ul>
*
* @param nums 整数数组
* @return 最大数和最小数的最大公约数
*/
public int findGCD(int[] nums) {
// 第一步，求得数组中的最大数和最小数
int max = nums[0];
int min = nums[0];
for (int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 第二步，不断辗转相除
return gcd(max, min);
}
/**
* <p>求两个数的最大公约数，利用辗转相除法。</p>
*
* @param a 第一个整数
* @param b 第二个整数
* @return 最大公约数
*/
private int gcd(int a, int b) {
int max = Math.max(a, b);
int min = Math.min(a, b);
if (max % min == 0) {
return min;
}
return gcd(max % min, min);
}
}
解法3
public class Solution {
/**
* <p>思路：更相减损术：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
* 例如10和25，25减10的差是15，那么10和25的最大公约数，等同于10和15的最大公约数。由此，我们同样可以通过递归来简化问题。
* 首先，计算出a和b的差值c（假设a>b），把问题转化成求b和c的最大公约数；然后计算出c和b的差值d（假设c>b），
* 把问题转化成求b和d的最大公约数；再计算出b和d的差值e（假设b>d），把问题转化成求d和e的最大公约数……</p>
* <p>结果：成功</p>
* <ul>
* <li>执行用时：1 ms, 在所有 Java 提交中击败了67.14% 的用户</li>
* <li>内存消耗：37.6 MB, 在所有 Java 提交中击败了99.84% 的用户</li>
* <li>通过测试用例：215 / 215</li>
* </ul>
*
* @param nums 整数数组
* @return 最大数和最小数的最大公约数
*/
public int findGCD(int[] nums) {
// 第一步，求得数组中的最大数和最小数
int max = nums[0];
int min = nums[0];
for (int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 第二步，不断更相减损术
return gcd(max, min);
}
/**
* <p>求两个数的最大公约数，利用更相减损术。</p>
*
* @param a 第一个整数
* @param b 第二个整数
* @return 最大公约数
*/
private int gcd(int a, int b) {
if (a == b) {
return a;
}
int max = Math.max(a, b);
int min = Math.min(a, b);
return gcd(max - min, min);
}
}
解法4
public class Solution {
/**
* <p>思路：把辗转相除法和更相减损术的优势结合起来，在更相减损术的基础上使用移位运算。思想如下：
* <ul>
* <li>当a和b均为偶数时，gcd(a,b) = 2×gcd(a/2, b/2) = 2×gcd(a>>1,b>>1)。</li>
* <li>当a为偶数，b为奇数时，gcd(a,b) = gcd(a/2,b) = gcd(a>>1,b)。</li>
* <li>当a为奇数，b为偶数时，gcd(a,b) = gcd(a,b/2) = gcd(a,b>>1)。</li>
* <li>当a和b均为奇数时，先利用更相减损术运算一次，gcd(a,b)=gcd(b,a-b)，此时a-b必然是偶数，然后又可以继续进行移位运算。</li>
* </ul>
* </p>
* <p>例如，计算10和25的最大公约数的步骤如下：</p>
* <ul>
* <li>1. 整数10通过移位，可以转换成求5和25的最大公约数。</li>
* <li>2.利用更相减损术，计算出25-5=20，转换成求5和20的最大公约数。</li>
* <li>3. 整数20通过移位，可以转换成求5和10的最大公约数。</li>
* <li>4. 整数10通过移位，可以转换成求5和5的最大公约数。</li>
* <li>5. 利用更相减损术，因为两数相等，所以最大公约数是5。</li>
* </ul>
*
* <p>结果：成功</p>
* <ul>
* <li>执行用时：1 ms, 在所有 Java 提交中击败了67.14% 的用户</li>
* <li>内存消耗：38 MB, 在所有 Java 提交中击败了86.11% 的用户</li>
* <li>通过测试用例：215 / 215</li>
* </ul>
*
* @param nums 整数数组
* @return 最大数和最小数的最大公约数
*/
public int findGCD(int[] nums) {
// 第一步，求得数组中的最大数和最小数
int max = nums[0];
int min = nums[0];
for (int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 第二步
return gcd(max, min);
}
/**
* <p>求两个数的最大公约数，利用更相减损术。</p>
*
* @param a 第一个整数
* @param b 第二个整数
* @return 最大公约数
*/
private int gcd(int a, int b) {
if (a == b) {
return a;
}
/*如果a和b都是偶数
if(a%2==0&&b%2==0){
return gcd(a/2, b/2)*2;
}
*/
if ((a & 1) == 0 && (b & 1) == 0) {
return gcd(a >> 1, b >> 1) << 1;
}
/*如果a是偶数，b是奇数
else if(a%2==0&&b%2!=0){
return gcd(a/2, b);
}
*/
else if ((a & 1) == 0 && (b & 1) != 0) {
return gcd(a >> 1, b);
}
/*如果a是奇数，b是偶数
else if(a%2!=0&&b%2==0){
return gcd(a, b/2);
}
*/
else if ((a & 1) != 0 && (b & 1) == 0) {
return gcd(a, b >> 1);
}
/*如果a和b都是奇数
else(a%2!=0&&a%2!=0){
int max = Math.max(a, b);
int min = Math.min(a, b);
return gcd(max - min, min);
}
*/
else {
int max = Math.max(a, b);
int min = Math.min(a, b);
return gcd(max - min, min);
}
}
}
